ICPC2021国内予選参加記
チーム Royal Blue としてICPC2021国内予選に参加しました。
私としては5度目の参加で最後のICPC大会になります。
チームメイト
開始前
家に16:00頃に着く。
16:30開始なので部屋の整理とお菓子のチョコレートの準備をし、16:15頃からチームと通話をつなぐ。
とりあえず4完を全力で頑張ろうという感じで準備していたらいつの間にか開始時間になっていた。
大会本番
16:30と同時にコンテストページを更新するとアクセスできず「おや？」となる。（去年もこんなことがあったような...）
ちょっとすると本番の問題一覧が表示された。
初動はAをRogi、Bをmhrb、Cを自分が担当。
C問題は構文木が与えられて自由に根や子の配置を操作してよいので式を評価したときの値を最大化せよ、という問題。
とりあえず、根が固定なら葉から順に決まるのでよい。問題は根を取り替えるときで、頂点数 n が小さいなら根を全部試して O(n2)。でも、nが最大3*105くらいはありそうだしダメそう。全方位木DPをやれればできる...できるなあ。
でも、C問題で構文解析+全方位木DPは実装エグくないか...？
その間にAが通る。Bもちょっとバグってたぽいけど通る。
自分は「C考察はできたけど実装やばいので...後は任せます」とだけ報告してCの実装に張り付く。
Dを2人が通してくれることを祈る。
...
Cの実装に四苦八苦していると、いつの間にか開始1時間が経っていた。
もっと楽な実装の解法があるのではないかと疑心暗鬼になりながら順位表を眺めるとCを通しているチームが1桁程度しかいないことがわかり、「本当に実装するしかない」ことを確信する。
一方、Dは考察が難航しているらしく雲行きがよくない。
Cの実装途中で各ノードの最大値だけでなく、最小値も持たないといけないことに気づき、少し実装がやり直しになりつらくなる...
Cの実装がつらかったので気分転換にDの概要を聞く。ぱっと見では貪欲に降順ソートすればよさそうだけどSample2が反例らしい。たしかに...
...
開始2時間経過、ようやくＣのサンプルが通り、一通りの実装を終えたのでテストケースを実行させる。 しかし、実行が終わらないケースを発見する。無限実装編から無限デバッグ編へ突入...
チームメイトにCのコードを投げつつコードとにらめっこをしていると、
for(auto i : vec){ ... for(auto i : vec){ ... } }
みたいなヤバい個所を発見し(？？？)、内側のループを消すとテストケースが秒で終了する。 提出すると無事AC！(開始2時間30分経過)
残り30分しかなく、全力でDが解けることに賭けることに。
Rogi君が貪欲で通らないSample2の解を全列挙してくれていて、
4 3 3 3 3 4 3 3 1 3 4 3 3 3 4 3 3 1 3 3 4 3 3 4 3 3 1 4 3 3 3 3 1 4 3 3 3 4 3 3 3 1 4 3 3 3 3 4 3 3 1 4 3 3 3 3 1 4 3 3 4 3 3 3 1 3 4 3 3 4 3 3
をぐっと睨むと、周期3でなにかあるっぽい。
試しに mod3 で和をとってみると割と平均化されているっぽい...?
数列を3等分...?
3つの箱を用意しておいて値を順次加算していく。1操作ですべての箱の値を-1する。操作回数の最大値は...?
値を3つの集合に分割したときの総和の最小値の最大化！→ DP！→ 解けた！！！
この解法を思いついたのが終了15分前くらいで、思いついたときは本当に体が震えた。 急いで解法を2人に共有し、 「～で解けました。え、僕の言ったこと分かりましたか？じゃあ全員同時実装して一番早かった人が出しましょう！」 で実装を始める。
実装を終え、終了3分前くらいでサンプルが合う！！！
自分が一番早かったっぽいのでテストケースを実行する。
そしてテストケース1が...通った！！！ （このときもう感情がやばかった*1）
急いでテストケース2をダウンロードして実行する。
そして...AC！！！
提出する瞬間はマウスを握る手が震えて、心臓はバクバクして音が耳から聞こえそうだったしヤバかった。通った瞬間は歓喜のあまり叫んだ。
実際にDが通ったのは終了51秒前だった。
結果
チーム Royal Blue の順位は ABCD 4完 38位 (学内1位) でした。
順当に行けば無事に国内予選突破です！
大会後
自分のDのサンプルがあった直後にRogi君も実装が終わったらしく、後にテストケースを試した感じACっぽいらしい。最悪私がWAでもなんとかなっていたのかもしれない。
同じ大学のチームの方々と感想戦をして、解法の共有だったりEの考察を話したりした。Dのブザービートを決めて興奮してたのでちょっとうるさかったかもしれない。
感想
過去最高にギリギリの4完だった。最後通ったのでめでたしだけど、試合経過2時間30分くらいまで絶望だった。大会後の感想戦の感じだと、もう少し時間の使い方を良くすればEも通せていた気がする。
反省点としては、自分がずっと2時間半もCに張り付いていたせいでDの考察を手伝えずチーム全体が停滞してしまっていた。今回オンラインで通話をつないでの参加でしたが、ちゃんと連絡を取り合わないとチームメイトが何をしているかわからないので、気を付けないといけないなと感じた。
とはいえ、最後のICPCでも国内予選を突破できたのはめっちゃくちゃ嬉しいし、終了1分前にDを通せたのはめちゃくちゃ熱かった。 連絡手段がチャット・通話のみという環境の中戦ってくれたチームメイトに感謝。皆さん横浜大会オンサイトで会いましょう。
*1:開始直後のシステム障害で1分終了時間が延長されていたのに気づいておらず、手元の時計だと残り1分を切っていた
