ICPCアジア地区横浜大会 2020 参加記

2021/03/16-2021/03/17に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーは碧黴さん、ゆきのんさん、僕です。

今年は新型コロナウイルスの感染拡大の影響で、オンラインでの開催となりました。それに伴い、ネット上の情報を自由に参照できたり、事前に用意したコード片を使用してもよいことになっていました。

チーム内でのコミュニケーションはSlackのみを利用し、すべてテキストベースで行いました。音声通話をしようかとの案も出ましたが、なんとなく消極的になっているうちに立ち消えていました。

コンテスト前

Aobayama_sugarstepのチーム練に便乗する形で練習していました。ありがとうございました。

1日目（03/16）

生活リズムが前にずれていて困っていました。午前2時半に目を覚まして、そこから眠れなくなって布団でゴロゴロしていたのですが、結局午前7時半に再度寝てしまったようで、次に起きたのが正午でした。なんとかセーフ。

prefixがAobayama_であるチームが2つ存在したので、チームごとの行動の際に混じったことがあったようです。が、それ以外は特に問題なく、学生証のチェックが終了しました。

開会式が終わって、practiceが始まりました。碧黴さんがA、ゆきのんさんがBを読むので、僕はCとDを読みます。どうやら昨年と全く同じ問題のようです。Cは二重階乗のオーダーで探索することを覚えていましたが、Dはあんまり覚えていなかったので、Dから解くことにしました。最短経路だけ取り出したグラフを考えたとき、ある辺について、そこを迂回するような経路が存在するか判定できれば良いです。橋の検出ライブラリを貼れば楽だったようですが、言いかえが思いつきませんでした。今回は始点からの距離を並べた列を作り、imos法で辺に対応する区間に加算して、対応する区間が2本以上の辺で覆われているかどうかで判定することにしました。一発AC。Cも適当に書いてAC。この時点でAとBも通っていたので、全完です。

practiceで速さを求めて全完しても虚しさがすごいです。そのあと、適当にWAやTLEを出してみて、何となくジャッジの挙動を確認できた気持ちになります。例えばreturn 1;でREになること、longが64bit整数であることなどは重要でした。

practiceの後に少しZoomでお話があって、今日の予定は終了です。夜は2Dセグ木のライブラリを作ったりしていましたが、午後10時くらいに寝落ちしてしまいました。

2日目（03/17）

午前3時半くらいに目を覚まします。しばらく布団でゴロゴロしていたのですが、今日は二度寝するとまずいので、起きることにしました。朝は食事した後TechFULのイベント問題を解いたりして過ごしていました。

Zoomに入る時間を間違えてギリギリになりましたが、何とか最終連絡を聞くことができて、いよいよコンテストです。

コンテスト

問題文：http://icpc.iisf.or.jp/past-icpc/regional2020/problems-2020.pdf

順位表：https://icpcsec.firebaseapp.com/standings/

C問題

碧黴さんがA、ゆきのんさんがBを読みます。僕は残りの問題を適当に開いて訳す感じで動こうかなと思ったのですが、C問題の問題名が「Short Coding」だったので、これは解くしかあるまい、としばらく時間を使って考えることにしました。

しばらく唸っていると、右手法（あるいは左手法）が使えることに気づきます。つまり、右手法を実際に再現するようなプログラムを書けば、どんな盤面でも必ずゴールできることになります。おそらく、かなり短いプログラムで再現可能で、それより短いプログラムについては全探索するというのが問題の意図なのでしょう。実際に手でいろいろ試していると、次のような5行のプログラムが完成しました。

RIGHT
IF-OPEN 5
LEFT
GOTO 2
FORWARD

サンプル出力が最大で5行であることからも、これが最短っぽいです。それ未満の行数のプログラムを全探索するコードを書いてサンプルを試してみると、出力される行数が一致していることがわかります。よさそうなので提出しましたが、WA。配列外参照していることに気づいたので直しましたが、またもやWA。コードをじっくり見ていると、右に曲がるときと左に曲がるときで方向を表す変数に足す値が逆になっていることに気づきました。そこを修正するとAC。45分でした。

CのFAはonionsの43分なので、ギリギリ負けたことになります。改めて以前のサンプルに対する出力を確認してみると、サンプル1から正しくない解を出力していることに気づきます。行数だけじゃなくてちゃんと内容にまで気を配っていれば……と後悔することしきりでした。しばらくはこれが頭にこびりついて離れなくなりました。

G問題

僕がCを解いている間にBが通っていました。Aはちょっと炎上していそうですが、あんまり触れずに次の問題に進みます。Dを読んで概要を共有しました。シンプルな問題ですが、とっかかりがつかめないので、次の問題に進むことにします。この時点ではGとHが2チームに、Jが4、5チームに解かれていたと思います。ゆきのんさんがすでにJを読んでいるので、僕はGを読むことにしました。ゆきのんさんはそのままJを書き始めていました。

Gの概要を共有してからしばらく考えていると、あるしきい値に対してそれ以下の頂点の数x、連結成分の個数aと、それより大きな頂点の数y、連結成分の個数bが与えられたとき、a+b-1<=min(x,y)が必要条件であることに気づきます。通され具合からこれが十分条件でもあると決めつけることにして、とりあえず実装します。

2021/03/18追記：解説でもこの部分の証明は飛ばされていましたが、そのとき話していた熨斗袋さんに帰納法が回るとの指摘を頂いたことを思い出しました。a+b>=3のときは、2つ以上の頂点からなる連結成分が必ず存在することがわかるので、その連結成分を適当につなげることにします。そのあと使った頂点を無視することで、不等式の両辺から1引いた問題に帰着できます。

xとyを求めるのは簡単です。aとbを求めるのには、しきい値をずらしながら一つのUFを更新するのではうまくいきませんが、しきい値以下の頂点としきい値より大きい頂点に分けてそれぞれ計算すればうまくいきそうです。そのようにして実装してみるとサンプルが合ったので提出、AC。78分でした。この数分前にJも通っていました。

H問題

Aのコードが共有されてきました。改めて以前のやり取りを読み返してみてもどういうロジックなのかよくわからなかったので、各座標(x,y,z)について3方向の影を調べてブロックの存在判定をし、最後に条件を満たしているかチェックする、という方針に書き換えてもらうことにします。入力される文字列と座標の対応がややこしいですが、座標軸に合わせて考えることにすると、それぞれどの方向に軸が存在するか描かれた図を使うことで比較的簡単に変換の式が得られます。

書き換えてもらっている間にIを読んで概要を共有します。数え上げですがすぐにはわかりません。ゆきのんさんがHを読んでいて、そちらの概要も共有されてきました。こっちはクエリに答える問題なので、とっかかりは楽そうです。Hをしばらく考えることにします。

素因数ごとに独立に考えるのは明らかです。10³以下の素数の個数を数えると168個でしたが、168本くらいならセグメント木を持ってもよさそうな気分になります。素因数の指数を小さいほうから3つ持つようなセグメント木を書けば、実際に答えにおけるその素因数の指数を計算することができそうです。定数倍が怖いですが、TLが10secもあるので多分大丈夫だろうという気持ちになりました。

残るは10³以上の素数についてです。これは、区間の先頭k+1項に含まれるような素数しか候補となりえないため、それぞれチェックしてよさそうです。チェックの方法についてですが、事前に10³以下の素因数を持たないようにしておいた数列に対して区間==を計算するようなセグメント木を作ってその上で二分探索すれば、ある素因数が出現する区間を求めることができるので、k+1回繰り返せば間k個を抜いたような区間の右端が求まります。

この時点でAが通っていたと思います。解けたので書くことにします。サンプルが貧弱で、10³以上の素数が必要となるケースが存在しなかったので、自分で適当に作って足しました。しかし依然貧弱なままだったようで、例えば等号付き不等号の等号が抜けていたり、l+i項目を見ようとしてi項目を見てしまったりなど残念なミスで2WAを重ねました。結局147分時点でAC。

I問題

E問題の概要が共有されて、見覚えがあるという話がされていました。確かに僕も見たことがある気がします。

後からTLで知りましたが、JAG夏合宿2018day1Eらしいです。これは確か、どこか海外のICPC予選セットだったと思います。なのでAOJを探しても収録されていないわけなんですね。

Eを解こうとして、円の半径をにぶたんすれば良いと分かったのですがWA、多角形が円の半分に偏るコーナーケースにゆきのんさんが気付いたのが残り15分時点で、実装できませんでした…。

JAG夏合宿・ACPC2018 参加記 - kotatsugameの日記

角度を足して1周ぶんになるかを見ること、円の片側に多角形が寄った時の処理が難しいこと、などが思い出されました。適当に立式して二分探索すれば解けそうであることが分かったので、ゆきのんさんに任せて、自分はIに挑みます。

まず、入退室が両方記録されているIDは無視してよいです。それ以外を考えます。

制約がn<=5000なので、1次元足したdpをするのだろうなという気持ちになります。入室の際にIDがわからない人にIDを割り振ってしまうと、入室と退室でそれぞれ1つずつ情報を持たなければならない気がします。ここで、退室のときに入室まで遡って割り振ることにしてみると、情報が1つだけでよいような気がします。まだIDが割り振られていない人が室内に何人いるか、の情報を足す1次元で持つことにして、実際に書いて様子を見ます。直感的に、それ以外に必要になるような値はすべて適切な前計算と組み合わせて導出できる気がします。

dp[i][j]で、今i番目の記録を処理していて、室内にIDが割り振られていない人がj人いる場合の通り数を表すことにします。まず入室処理についてですが、これは、IDが割り振られている人が入室するか（dp[i+1][j]+=dp[i][j]）、そうでない人が入室するか（dp[i+1][j+1]+=dp[i][j]）の違いになります。特に係数が掛かったりはしません。

次に退室処理についてです。退室する人のIDがわかっているときは、室内にいるIDが割り振られていない人のうち1人を選んでIDを割り振ることになるため、係数にjがかかってdp[i+1][j-1]+=dp[i][j]*jとなります。IDがわからないまま退室するときは幾分複雑で、

• 室内にいるIDが割り振られている人が退室する

現時点での室内の人数kが前計算でわかるので、dp[i][j]+=dp[i][j]*(k-j)です。

• 室内にいるIDが割り振られていない人が退室する

室内にいるIDが割り振られていない人のうち1人を選んでIDを割り振るのは、先ほどと同じです。ただ今回は割り振るIDにも自由度があります。入退室のどちらにも記録されていなかったIDの個数のうち、現在すでに使われているIDの個数（つまり、IDが割り振られていないまま入室して、IDがわからないタイミングで退室していった人数）を求めましょう。IDが割り振られていないまま入室して、現在すでに退室していった人の人数は(これまでに入室したIDが割り振られていない人)-j人です。IDがわかるタイミングで退室するときは、必ずIDが割り振られていないまま入室した人から選ばれることがわかりますから、IDがわからないタイミングで退室していった人数は先ほどの値からさらに引いて(これまでに入室したIDが割り振られていない人)-j-(これまでに退室したIDが割り振られている人)人です。

かっこで示した値や「入退室のどちらにも記録されていなかったIDの個数」は前計算でわかるので、割り振るIDの自由度rが求まり、dp[i][j-1]+=dp[i][j]*j*rです。

これでサンプルを試すと合いました。この問題のサンプルもかなり貧弱に感じられますが、とりあえず提出してみると、AC。189分でした。

E問題

円の片側に多角形が寄っているとき微妙に変な値が出る、とのことで、ゆきのんさんのコードが共有されていました。適当に口出ししながらK問題を読みます。適当なdpを考えて実装したらサンプルが合ったので、チームメイトに何も言わずに提出したのですが、WAでした。いくつか証明をしていない性質を仮定して解いたので、仮定が間違っていたんだなあとはわかりますが、具体的にどういうケースで壊れるのかはわかりません。K問題は頑張っても通りそうにないので、E問題を通すことに集中することにしました。

コードをコピペしてきて手元で動かしていろいろやっていたら、サンプルが合ったので提出しました。するとゆきのんさんもほとんど同時に提出していたらしく、どちらもACしました。239分でした。両方通ったからよかったものの、例えば僕のコードがWAで、しかも微妙に僕のほうが早く出していた、みたいなことになったら目も当てられません。ここははっきりとコミュニケーション不足が表れました。

ゆきのんさんは誤差に苦しんで、結局acosをasinに変更したらサンプルが合ったそうです。僕はacosのままでしたが通ったので、よくわかりません。Heno Worldも誤差で苦しんだという話をしていたのですが、僕自身はそういう感じがしないので、どこかの実装方針が違ったんだろうと思っています。しかし自分のコードもよく見るとEPSとEPSを10倍した値の2種類を使い分けている箇所があるので、たまたま1回目の提出で当たりを引いただけなのかもしれません。

残り

K問題を解いていました。現在の方針は、文字列の先頭にTのprefixを繋げていくdpで、繋げるときのスコア計算をZ-algorithmで行うものです。つなげる先がどのような文字列かわからない状態でスコア計算をするのはかなり怪しいですが、Tが繰り返されていると考えて大丈夫だろうと思い実装していました。しかしWAが取れないので、どうやら大丈夫ではないようです。しかしどのようなケースで落ちるのかが全然わからないため、ojでランダムケースによるテストをしてみました。すると、うまく愚直解と異なる答えが出るものが見つかりました。

bbcbbbcc
8

とりあえず、Tが繰り返されていると考えるスコア計算が実際にダメであることがわかりました。ここで、先頭に繋げるprefixの長さは広義単調増加するだろうと考え、現在どの長さのprefixを繋げたかも持つ3乗のdpを書いてみました。今度は上のケースにも通りましたが、当然TLEしてしまい、高速化をしようにもうまくいかず、そのままコンテストが終了しました。

コンテスト後

Gather Townに集まって話しながら解説を聞きました。K問題はオートマトン上でdpするらしいです。そう言われると見たことあるなあという気持ちになってしまうのですが、次見たときに解けるかどうかはちょっと怪しいです。その後YesNoを見ました。自分のチームのKへの提出が通っていないのは知っているのですが、実際Noとなる瞬間を目にすると非常に残念になります。

途中送った顔写真が公開されるフェーズがあったのですが、僕は（ほとんど故意に）送り忘れていたので、いらすとやの画像に差し変わっていました。みんな提出していないものだと予想していたのですが、かなりの人数が自分の顔面を提出していて本当にびっくりしました。

YouTubeLiveの放送が終了した後は、Gather Townが閉まるまでずっと喋っていました。途中からピクトセンスを始めたのですが、通話しながら遊ぶのは非常に楽しかったです。小学生みたいな下ネタで笑うのも楽しいです。

ピクトセンス最高！！！ pic.twitter.com/9TvZLMArQy

— こるとん (@kyort0n) 2021年3月17日

結果

8完10位でした。例年と単純に比較すれば良い成績であると喜ぶところですが、今年は並列可能になったり海外チームがいなかったりネット検索が可能だったりといろいろ勝手が違うので、ちょっとモヤモヤはします。とりあえず3年間順位が単調減少しているので、来年は1桁順位を取れるよう頑張りたいです。