ICPC国内予選 2020 参加記 - さかなの思い

結果

全体12位、学内3位で予選通過しました。

前日まで

卒業研究にかなり精神力を費やし、競プロをする時間も気力も確保できない日々が続いていた。

当日、開始前

コミュニケーションを重視していたので、当日は僕の家に集まることになった。
部屋の掃除とかを両親が手伝ってくれました。感謝......

一方その日は13時から研究室の輪講もあったので、発表の緊張＋大会の緊張で、1日中ソワソワした気持ちが続く。

そして、合流

駅前で合流し、家に向かう。
２人曰く「この辺は都会という感じがする」らしい。普段住んでいると全くそんなことは感じなかったが（事実、渋谷や新宿と比べると全く都会感はないが）、意外と他の人から見るとそういうものなんだろうか

家につき、環境のセットアップを行う。環境に慣れるために鎖中経路をACした。

開始

問題が見れない。
３人一緒だったこともあって、ほとんど焦る気持ちはなかった。自分たちのチームだけが問題見えなくても後で抗議すればどうせなんとかなるだろうと気楽に考えていた。むしろ、URLを勘違いしていないかとか、そういった「抗議してもどうにもならないミス」の方が気になった。

我々のチームは、ABCに２人、D以降に１人という特殊な配置をしていた。個人的には模擬国内も今回もこの作戦はハマったんじゃないだろうかと思っている。

Aを読み、実装を始める。序盤の問題でペナをつけることが一番やってはいけないことだと自覚していたので（参考：2019国内予選A）、かなり慎重に実装し、AC。

Bはokuraが実装していたので、Cを読む。やることは簡単だが、計算量解析が全くできない。（計算量解析の難しい問題は苦手分野だったので、今思うとこの時点で他人に投げるべきだったのかもしれない。）とりあえず愚直な実装をしてみると、案外100ケースくらいは簡単に通ったのでしばらく待ってみるが、100ケース目以降がやたらと遅いので、どうやらこの方針ではダメそうだろうと思い、考え直す。

いろいろ枝刈りをしていたが全て徒労に終わったので、最終的には、最初に約数列挙して二重ループを回すことにした。それでも遅いが、さっきよりは改善されているっぽいのでそのまま待ち続ける。そしてAC。この頃にはDが通っていた、FAらしい（すごい）。

EやFを読み、問題の考察をする。自分は終始Eを考えていた。（Fがグラフなので。）

全くわからなかったが何チームかは通しているので、どうせ「全探索すれば意外と間に合う系」なんだろうと決め打って、真ん中で分割しながらDFSをすることにする。

今考えると明らかに間に合うはずがない解法なのだが、実装していた当時の僕は、（計算量は重いかもしれないが、実行を待っていればなんとかなるだろう）と気楽に考えて実装を始めてしまう。結果としては、最後まで実装が終わらずにサンプルすら合わないままコンテストが終了し、悔しい思いをした。途中でMisterがFを通してくれたのでなんとか5完でき、Dが早かったのでなんとかペナルティ差で学内3位という成績に滑り込むことができた。

余談だが、僕は終了してからも自分たちのチームが勝ち抜けたことに気づいておらず、完全に落ち込んでいた（例年、東大は10位以内に3チーム以上入賞することが多く、事実上東大チームにとっては勝ち抜け条件が「上位10チームに入賞すること」となっていたため）。終わった数分後に勝ち抜けた事実に気付いたのだが、Misterは終わる前から気付いていたらしい。「なぜ言わなかったの？」と聞いてみたところ「だって言ったらEの実装やめちゃうかもしれないじゃん」とのことだった。草。

終了後

TLを眺めながら感想戦をしたあと、3人で近所のレストランで夕食を食べて帰ってきた。せっかく勝ち抜けたんだからもっと豪華なところに行ってもよかったかもしれないとも思った。

反省

上の参加記からも分かる通り、今回は個人としては何も活躍できなかった。Cで苦戦してしまったり、Eの嘘解法にほとんどの時間を費やしてしまったりして、戦犯と言ってもいいくらいの酷いパフォーマンスだった。チームが勝ち抜けたのにこんなに悔しい思いをするとは思わなかった。