ICPC国内予選2024参加記（noya2視点）

はじめに

ICPC（国際大学対抗プログラミングコンテスト）という大会の2024年度国内予選に「AMATSUKAZE」というチームで参加しました。気づいたら優勝していました。ありがとうございます。

チーム編成

noya2(この記事を書いている本人)
- B3
- 幾何・ライブラリ担当
shobonvip
- B4
- フロー・構文解析担当
- タイピングが超速い
Hemimor
- M2(早生まれ)
- 天才・数学担当
- すべての考察が速い

チーム結成秘話

前年度の AMATSUKAZE は　ebi_fly さんが年齢制限により引退し、今年度に向けてメンバーを探している状態でした。

と見せかけ、今年の 3 月にベトナムで行われたプレーオフに参加した際に、チームは結成されていました。

チーム tonosama が World Final への出場を決め、それに伴ってメンバーの一人を除いて ICPC 引退が決まっていたので、その残ったメンバーと組みたいと心の中では思っていました。その方とはあまり面識がなく、そういう流れに持っていくのが難しそうだったのですが、幸運なことに、その方から私たち（noya2 と shobonvip）に声をかけてくれて、そのときにチームは結成されていたという話です。

練習など

2 週間に 1 回程度、対面で集まって Codeforces の gym から ICPC らしきセットを選んで走っていました。そのころはライブラリはタイピング想定だったので、そのつもりで練習していました。

あるとき、国内予選のルールが変更され、ライブラリの使用がOKになりました。それからの練習は、すべて国内予選ルールに切り替えました。

NPCAPC にチーム参加しました。

Universal Cup の第 3 期が開催され、我々のチームも参加することにしました。

5h 級は基本的にオンラインで参加していました。

直前の 1 ヶ月は、tatyam さんが今回の国内予選ルールの仕様で作ってくれたジャッジを利用して、2018~2020 の国内予選を走りました。かなりためになったと思います。ありがとうございます。

6/30 模擬国内予選

7 完 4 位でした。悪くない動きだったと思います。 shobon さんの調子がかなり良く、実装をガンガン進めて、埋め込んだバグをパクパク取り除いて、AC まで辿り着く、で駆け抜けていった印象です。

自分は B,E を解き、 F のすべての考察を shobon さんに投げ、G の誤読をし、 H でハッシュ解法を提案しました。

7/5 国内予選

そこそこ覚えているので、時系列順に書きます。

競技開始

画面を横に分割し、問題文とエディタを表示します。問題文が印刷されるまでは、画面に映る一問をみんなで見つめる、ということになります。

A

shobon さんの担当です。やればよいらしいです。マウスの所有権を noya2 がもらい、B を見ます、と思ったところで A の実装が終わり、ACまでサクサク行きました。 0:02:10

B

noya2 の担当です。やります。直前の状態をきちんと保存しておけば、正しく判定できそうです。 Hemimor さんが C 問題を読み終わるのとほぼ同時に実装が終わり、ACまでサクサク行き。0:07:59

C

Hemimor さんの担当です。六角グリッド上の距離らしいです。　自分は丸暗記していたので、Hemimor さんが思い出すより先に式を伝え、実装は任せました。ACまでサクサク。0:10:43

D

shobon さんの担当です。まだ問題文が届きません、助けて〜。やることは単純ですが、バグりそうと言いながら書き始めていました。shobon さんは、爆速で実装し、いくつか埋め込んだバグを爆速で取り除く、というスタイルなのですが、PC を占有してほしくないので、ザッと実装してバグった後にいったん印刷してPCを開けてもらいました。

このあたりで問題文が届きました。

E

noya2 の担当です。両端が同じ色の場合は簡単です。違う色の場合は、最も先に出てくる末尾の色と、最も後に出てくる先頭の色の位置を比べる必要があります。Noの判定は簡単ですが、Yesと言うのは難しそうです。とはいえ、どうせ構築できてしまうので、コネコネしていると構築できました。公式解説と同じものになります。丁寧に実装すればいいので、バグった D に変わって実装を始めました。

D の修正が何度か飛んできて、そのたびに席を交代して、大変でした。5度目くらいの修正で D のサンプルが通り、そのままACまでサク。 0:35:42

その後、E が無事書き終わり、サンプルも合いましたが、見た目がやばく、沼にはまると大変だと見えていたので、チェッカーを書く判断をしました。多少時間をかけましたが、安心感が違います。結局もとの実装にバグはなかったのですが、とにかく通りました。 0:47:51

そこそこ速い自信があったので、ここで順位表をチラ見します。 1 位でした。まだ気は抜けないけど、余計な焦りはここで消えたような気がします。

F以降

Hemimor さんが解けそうだと言って shobon さんと相談していましたが、どうやら変なケースや厄介な実装が目に見えて、辛そうでした。3 人でハマるとよくないので、あまり首を突っ込まないようにします。 shobon さんがとにかく実装してみると言っていたので、とりあえず任せることにしました。

G を見ます。面白そうですが、こういうのは Hemimor さんが得意そうです。問題概要を伝えると、自分はよくわからないですが考察が進んだらしく、いけるんじゃないか？となります。自分は解法を聞いて相槌を打つ役をしていました。

Fの実装が終わって、バグを取り終えて、サンプルがあったらしいです。WA は回避してほしいと伝えたら、もうできることないしテストケース走らせていいですか？と言われてしまったので、まぁ任せます。なんか通ってウケていましたが、とにかく shobon さんがすごすぎる。ありがとうございます。　1:10:39

順位表をチラ見すると、 1 位でした。2

Hemimor さんに G の実装に移ってもらいました。G の解法はそのときは理解していなかったのですが、とはいえ条件整理を丁寧にやればちゃんと詰められる問題だとは思ったので、ここは　Hemimor さんを信用して自分は H 以降を見ます。

H は問題文に英語が混じっていました。問題名が「とおせんぼ」だったので、なるほどね、英語問題文が日本語問題文をとおせんぼしてくるわけだ、と妙に納得していました（普通にあっち側のミスだったらしい...）。題意を理解すると、制約の小ささもあって、フローとかそういうやつじゃないか？となります。フローの担当である shobon さんに問題内容を共有します。

しばらく考えていましたが、解ける気がしないという気持ちになります。ここで数十分。

しばらくすると G の実装が終わり、サンプルもあったそうです。が、いくらか変なケースを考えて落ちるケースを見つけ、多少のデバッグをしていたようです。自信が満タンになったらしく、ランダムチェック書きませんか？と伝えたところ、いけると思うと言われてしまい、えー、テストケースをダウンロードして実行します。なんか通りました。すごすぎる。ありがとうございます。 1:42:52

順位表をチラ見すると、 1 位でした。3

明らかにチームメンバーの調子が良かったので、自分が何もしなくても問題が通されていて、すごいです。何か貢献をしたいのですが。

Iも見ますが、謎です。Hemimorさんと考察をしますが、お互い手がかり掴めずと言った感触で、あまり解けそうにありません。ふと順位表を見ると、いつの間にか 3 位になっており、I が解かれていました。そんな〜

Hの方が望みがあると思ったので、I を Hemimor さんに任せて　shobon さんと H の考察をします。

はじめは、 Alice の最適戦略についての考察などをしていたのですが、自分はそれは筋が悪いと思ったので、連結性条件に注目する方針を共有しました。すると、 shobon さんから、非連結にするために盤面を横断する壁を作る案を出してもらいます。自分は、大胆予想として、 3 つ以上の禁止マスが協力してピースの進路を妨害するということは起こり得ず、 2 つの禁止マスがその間をピースがすり抜けるのを妨害することに帰着できるのではないか？と伝えます。これなら最短経路問題にできるからです。すると、shobon さんから、すり抜けが妨害できる必要十分条件はピースの 8 近傍を見ればいいのでは？という大胆予想をもらいました。自分目線では大胆予想に見えましたが、 shobon さんにとってはかなり確信に近かったようです。この時点で実装に移ってもらいました。

自分はそこそこ実装方針を詰めてから実装に取り掛かるタイプなのですが、shobon さんは実装しながら実装方針を練っていく感じらしく、それでも異常な速度で実装していくので、見ていてとても頼もしいです。かくして、H問題も、もう少し詰めたい noya2 よりも先に shobon さんが実装に手をつけるということになりました。

多くのバグが埋め込まれましたが、ついに解消し、サンプルも通り、いざテストケースを実行して提出すると WA が返ってきます。2:28:42 そんな〜

自分は、shobon さんの提案した必要十分条件を疑っていたのですが、 shobon さん的にはそこに疑いはないらしく、他のバグっている箇所を探していました。結果的には、その必要十分条件を正しく実装できていなかったのと、他にもバグっていました。それを直し、大量の紆余曲折を経て、もう一度まともなコードが出来上がりました。テストケースを走らせ、提出を試みます。

自分視点では危ない橋を渡っていると思っていたので、 WA が返ってくることを予想していたのですが、なんと、 AC が返ってきます。なるほどね、ほう。とはいえ TLE なので、追加のテストケースを走らせます。まぁ、通るんですよね、はい、通りました。すごい。2:51:56

3 位になってしまったのを確認した後、なんとか 8 完したいよねという話にはなっていました。達成できて、すごいです。自分は何もしていませんが...

ところで、順位表を見ると、なんとまたまた 1 位にあがっていました！　7 完がかなり早かったおかげで、 8 問目が多少遅かった分は許されたようです。残り 8 分はお祈りです。

H の考察は I から撤退した Hemimor さんにも聞いてもらっていたのですが、必要十分条件パート以外は正しそうと言ってくれました。正直なところ、証明：ACなので、モヤモヤという気分です。嘘解法だったら嫌だなぁと思っていたのですが、終了後に noshi91 さんに正当性の証拠となる高度典型を教えてもらい、ホッとしたと同時に、勉強にもなってお得な気分になりました。

コンテスト終了

そのまま優勝してしまいました。チームメンバーに支えられました。嬉しいです。その場にいた他の東工大チームの人たちに祝ってもらいました。ありがとうございます。

今後

12 月に横浜で開催されるアジア地区予選に出場します。それまで、チーム練と個人練で実力を磨いていきます。