ICPC2021国内予選参加記 - Last AC -

ICPC国内予選2021の参加記です。

筑波大学からチームfib-dih（pengin, amixedcolor, pointN） で参加してました。

前日以前

筑波大学という新しい環境になったので、かつてのkibisiのメンバーであるngng628とwakasukiはもういません。ということで、チームメイトを募集しました。声をかけやすい人の中で僕がいちばん強いと認識しているpenginさんにICPCのチーム決めについてTwitterのDMでそれとなく話しかけ、自然な流れでチームに引き込むことに成功しました。もうひとりは部のチャットで誰でもいいので組んでくれと呼びかけたところ、最速で返事が来たamixedcolorさん（以下amixさん）に加わってもらいました。彼はICPCは初めてだそうです。

チーム名はわりと適当に決めました。各自が好きな英小文字を2字ずつあげ、amixさんがそれを並び替えました。fib-dihはフィボナッチ情報本部の意味です。ICPCの問題文とノリが似ていますね。この6文字のうち、僕はbとiを宣言しました。kibisiのbiです。誰がkiでbiでsiみたいなのはないんですが。むしろ全部wakasukiのものだし。

僕はC++を使っているのですが、penginさんはC言語、amixさんはAtCoderの提出を見る限りではPythonのようで、ということはソースコード自体の共有は期待できないな、みたいなことを思っていました。

前日

木曜日です。メンタルに悪い影響を与えるのでオンライン授業は全部後回しにしました。研究室配属希望登録の時期と重なったのでそれはちゃんとやりました。チーム一覧で筑波大学内のライバルを確認したところ、shichifuku（前回予選突破してる強いところ）とkarintou_extra（前回kibisiより少し上の順位だったところ）の2チームしかいませんでした。去年に比べて明らかに少ないので、例年に比べれば突破の可能性はじゅうぶんあると思いました。とはいえ学内にライバルがいるので高専時代よりもボーダーは高くなるのですが。リハーサルを夜にやって、そのあと国内予選2020-Dを通して早めに寝ました。

当日

金曜日です。学園祭のため、授業はありません。ラッキー。Twitterを見るなどしてゆったり過ごしました。3時ぐらいになって準備を始め、3時半ぐらいに家を出ました。大学に着いたらもう他のチームが揃っていたので驚きました。部屋の奥のほうにshichifukuと思しき人たちがいて、手前にkarintou_extraの人たちがいました。暇なのでkarintou_extraの人たちと話をしました。去年とメンバーが違うらしく、去年のデータがあてにならないことが判明しました。ちょっとしてからpenginさんも来ました。shichifukuと我々fib-dihが（じゅうぶん広い）同じ部屋、karintou_extraは別室で参加することになりました。

競技開始前

いちおう、amixさんも大学に来る予定だったのですが、来れなくなったとのことなのでpenginさんと初動について少し相談し、amixさんにAを任せました。ペナルティが20分で重いのがICPCの特徴なので、Aは慎重にねと念を押し、現場のpenginさんと僕はBCをいい感じにしようという方針にしました。D以降は手が空いた人から、という感じ。

本番

4時30分。全3時間の予選がスタートしました。開始直後、コンテストページが開けなくなっていましたが、去年もそうだったのでまたかという感じでした。今回初めてのamixさんに少し待てば開けるので安心してほしいと伝えるなどしつつ待っていると、すぐにコンテストページが開けるようになりました。Bを僕が開き、Cをpenginさんが開きました。Cは実装がめちゃくちゃ重いという感じらしく、方針は立ったようなのでお任せしました。Bは20分ぐらいで通りました。順位表を見ると、コンテスト開始時のエラーでコンテストは1分延長すると書いてありました。はい。penginさんが格闘しているCを見てみたのですが、明らかに重いことがわかりました。Aが通ってない様子だったのでamixさんに確認したところ、行けそうではあるが少し実装に手間取っているとのことで、Aを裏でこっそり並走しました。書き上げてサンプルが通ったのでAの様子を確認すると、1つ目のテストに通っていたので安心して後は任せました。Dを開いて読みつつ、Aを通したamixさんにDを考えてみてダメそうなら順位表監視をしてくれと言いました。言った直後、Dの簡単な嘘解法が思いついたのでそれをamixさんに共有しました。この時点ではCよりもDのほうが通っており、Cの異常さが際立つ順位表でした。またshichifukuがBでペナルティを食らっており、この時点では学内トップでしたが、開始1時間少しでshichifukuはCを通し（早い）、学内2位に落ちました。

それからしばらく経ちました。penginさんはかなりCの実装に苦戦しているらしく、そして僕もDの方針が全然浮かばず、かなり苦しい時間が流れました。2完はさすがにまずい。学内の他チームがどうこうとかじゃなくて、普通にやばい。Dの愚直を書いてみてエスパーしようとしてみたのですが、うまくいきません。途中penginさんとCDスワップみたいな話があったりしてpenginさんがDを触っていたのですが、正直Cは僕もきつそうなので実はDを中心に考えていました。順位表を監視しているamixさんからCとEが同程度に通っているということを聞いたりしましたが、EはEでうーんという感じで、まあ通すならDだろうと思っていました。

7時を過ぎ、予選は残り30分を切りました。Cは間に合わないので捨てました。マジで何も思いつかず、チームには絶望的な雰囲気が漂っていました。ふと順位表を見るとkarintou_extraが6時40分ごろにDを通していてfib-dihが学内最下位になっていることに気づきました。が、karintou_extraはそのDでペナルティを1つもらっており、さらにABのタイムを考慮すればまだ逆転の望みがあるという感じでした。

7時10分過ぎのことです。僕の頭にふと未証明の解法が浮かびました。正しい気もするししない気もして、計算量的には制約からするといい感じになりそうという感じでした。未証明ですが、もうこの際仕方ないので実装するしかありません。大急ぎで実装し、書き終えてサンプルを通したのが7時28分。急いでテストケースをダウンロードして手元で実行。その間に提出する問題を選択したりソースコードをアップしておき（Dなのにe.cppとかいうファイルに書いていたため慎重に選びました）、実行が終わったのを見て即座に提出。驚くべきことに1つ目のテストを突破しました。この時点で7時29分。penginさんが興奮する僕の様子を見て異様な雰囲気を感じ取ったようですが、構ってはいられません。2つめのテストケースをダウンロードし、同名保存できないのでファイル名を書き換え、実行コマンドの入力ファイル名も忘れずに変えて実行ボタンを押した、そのとき、、、

パソコンの時計に目を向けると、それはすでに7時30分を示していました。

…

…

…

…

…

いいえ、国内予選はまだ終わっていません。

大急ぎで2つめの解答を提出すると、画面にcongratulationsの文字が表示されました。予選終了30秒前のことでした。

予選が終わりました。順位表を見ると、fib-dihの提出は確かに通っています（僕のこの提出が、国内予選全体でいちばん最後に通された解答だったようです）。さらに、 karintou_extraを逆転していました。

終了後

少しして、karintou_extraの面々が別室から戻ってきました。頭に血が上り足が震える僕はいい試合でしたねなどと彼らに好き放題言い散らかし（ごめんなさい）、落ち着いてからいくらか会話を交わしました。karintou_extraもDは未証明エスパーだったようで、しかしながらこちらと全く同じ方針だったようです。

結果を見ると割と散々で、国内予選突破時のために持っておいたラーメン屋さんのクーポンを使うことにはなりませんでしたが、個人的には過去最高の結果でした。また来年、頑張ろうと思います。

追伸：shichifuku予選突破おめでとうございます、この先も頑張ってください

追記：ラーメン、翌週3人で食べに行った、amixさんとはこれが初対面、おいしかった