はじめに

ICPC 2024/2025 国内予選は noya2 さん、Hemimor さん、shobonvip の 3 人で AMATSUKAZE というチームで参加しました。
国内予選の結果は1位で優勝し、横浜大会への出場権を得ました！！

この記事を読んだ人はこの記事も読んでいます

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

はじめに ICPC（国際大学対抗プログラミングコンテスト）という大会の2024年度国内予選に「AMATSUKAZE」というチームで参加しました。気づいたら優勝していました。ありがとうございます。 チーム編成 * noya2(この記事を書いている本人) * B3 * 幾何・ライブラリ担当 * shobonvip * B4 * フロー・構文解析担当 * タイピングが超速い * Hemimor * M2(早生まれ) * 天才・数学担当 * すべての考察が速い チーム結成秘話 前年度の AMATSUKAZE は　ebi_fly さんが年齢制限により引退し、今年度に向けてメンバーを探している状態でした。 と見せかけ、今年の 3 月にベトナムで行われたプレーオフに参加した際に、チームは結成されていました。 チーム tonosama が World Final への出場を決め、それに伴ってメンバーの一人を除いて ICPC 引退が決まっていたので、その残ったメンバーと組

東京工業大学デジタル創作同好会traPnoya2

それまで

去年の AMATSUKAZE は noya さん、ebi さん、shobon のチームですが、ebi さんが去年で ICPC の出場権を使い切り引退しました。
そこで、ベトナムの ICPC playoff で ICPC 2024/2025 のチームについて話していたとき、去年 tonosama のメンバーであった Hemimor さんが入ってくれました。

東工大の ICPC 事情

東工大からは、今回の国内予選に 29 チームも参加しました。その中で黄色コーダー相当以上がいるチームが 6 チームくらいです。
東工大はホスト校なので通常の選抜から 1 チーム追加で国内予選が突破できます。しかし、AMATSUKAZE が東工大内最強候補とはいえ、問題数も時間も少なく分散が大きい国内予選では予選落ちする可能性は十分にあり、怖かったです。

ライブラリ

今回はルールが変更になり、ライブラリやテンプレートを最初から用意できるようになりました。ライブラリはできるだけ整備して使えるようにした方がいいと思います。とはいっても、ほとんどは AtCoder Library で足りました。

練習

練習は一週間に一回集まって 3 時間程度のセットを走りました。tatyam さんが本番とほぼ同じジャッジ環境を置いてくれたので感謝しながら活用しました。

模擬国内

6月29日（土曜日）、模擬国内がありました。模擬国内は4位でした。それまでの練習と同じように、担当は A→shobon、B→noya2、C→Hemimor、D→shobon、Eからは不定、という感じでした。

A～D

パソコンの左半分には問題文、右半分にはコードエディターを置くスタイルでやりました。 A は問題を読んだと同時に解けたので、 B を読ませながら A を書き、通りました。（0:03）

そして、noya さんが B を実装し、難なく通りました。（0:08）

Hemimor さんが C を実装している間、D 問題の問題文を自分が読み、少し眺めてすぐに解けました。ここらへんは覚えてないですが、D は実装が軽いのですぐに書けて、通りました。その後、Hemimor さんが考慮ミスで C で WA を出しましたが、すぐに修正して C も通りました。（0:40）

E～G

noya さんが E 問題に取り組んでいたので、 F 問題を読みました。

F 問題は noya さんがすでに解法を思いついていたらしく、「大きさが 2 べきである区間（これは 1 つにまとめることができるための必要条件）の個数が少ないこと」と、「スライムたちを 1 つにまとめられるかの判定も可能であること」、そして「答えは DP で求められること」を説明してもらいました。セグメント木を使えば楽に実装できそうなので、Fの実装を頭の中で固めます。

F の実装をする前に、G を読み、noya さんが「$(x+y{)}^2\ge x^2+y^2$ なので、分割を優先度付きキューで管理すれば解ける」と言ってくれました。しかし、実は制約で数列の要素の値が負になる可能性もあり、考え直す必要がありました。そこから Hemimor さんと並行で考えました。そして、「上位 K 個を持つ DP を考え、もらう DP において優先度付きキューで並列に取っていく」ことを思いつきました。G の解法を紙に書き、同時に noya さんが E 問題を 1 WA で通しました。この時点でランキング上位には AMATSUKAZE を含む東工大のチームが大量にいて、すごいと思いました。（0:59）

自分は F の実装を始めました。その後少しのバグを出しましたが、なんとか修正して通りました。（1:20）

そして、連続して G の実装を始めました。noya さんにランダムチェッカーを書くことを勧められたので書いてみると、愚直解と自分の解法が完全に一致していることが判明したので提出したら AC でした。 G 問題の FA かつ当時 1 位だったので嬉しかったです。15 分の速さで愚直解・高速解・ランダムチェッカーがほとんどバグなしで書けたのはかなり調子が良かったです。（1:35）

H, I

G を書いている間に H の議論が行われたようで、解法も出たようです。それによると、素数によるハッシュを考えるとよいらしい、ということらしいですが巨大な値の mod が必要で、modint を改変して 64 bit に対応しました。しかし、H 問題はどこかでバグっており正解に辿り着くことができず、コンテストが終了してしまいました……

その後、本番前に 64 bit modint が整備されました。

国内予選

当日は6時睡眠、13時起きです。14時に大学に着いたあと、他のICPC参加者と交流しました。また、wata さんの双対性スライドを印刷して持ってきたのでそれを読んでいました。

コンテスト開始が16時半なので、結構暇でした。zer0-star さんがレッドブルのライムフレーバーを飲んでいたので、自分も飲みました。16時くらいに Hemimor さんが来て、しばらくした後コンテストが始まりました。

A, B, C

A 問題は自分が見て、すぐに解けたので実装したら通りました。（0:02）

B 問題は noya さんが見て、すぐに通されてすごいと思いました。（0:07）

C 問題は Hemimor さんが見ました。このような六角形グリッドの最短距離は簡単に書けるのでその方針になりました。すぐに通されました。（0:10）

D, E, F

D 問題は自分が考察しました。「基本的には繰り返し検出だが、実装が難しい」と思いながらも実装を完成させました。しかし、コード中の assert に落ちてバグりました。

自分が実装をするときは、まず全体を完成させてしまうので、複雑な実装をしたときに「解法の大枠は合っているが、細かい部分でありえないミスがある」傾向にあります。

そのため、事前に「shobon が複雑な実装をバグったときはコードを印刷して頭を冷やす方がよい」という話を思い出し、「頭を冷やしてきます」とコードを印刷しに行き、noya さんの E 問題に交代します。印刷を眺めるとバグが次々に見つかりました。ここらへんで問題文の印刷も来ました。

noya さんが E を実装している間、たまに交代して 「D を修正しては、未だにバグがあることが判明すること」を繰り返すこと数回、ついに正しい答えが出てきました。そうして投げてみたら通りました。（0:35）

その後、F 問題を読み、 Hemimor さんから方針を教えてもらいました。「まずは盤面を鏡写しにして 2a×2b にする。ここで、ボールを動かす代わりにコインを動かすと答えの候補が 4 個しかないことがわかる。その後は、コインを動かした先にある最初のボールは何か？という問題になり、合同方程式に帰着される」という解法です。これは天才だと思いました。E 問題はその後すぐに通りました。（0:47）

Hemimor さんが F 問題の実装に自信がないらしいですが、自分はこの方針で通せると思ってたため、F を書くことにしました。途中で解法が思っていたものと少しだけ違うことが判明しましたが、修正が容易だったためそのまま修正して通りました。この時点で全体1位です。（1:10）

G, H

Hemimor さんと noya さんが G 問題を考えていて、解けたようなので G の実装を Hemimor さんがします。
その間は H 問題を読み、noya さんと一緒に考えました。直感で最小カット問題のような気はしますが、どういうグラフになるのか不明でした。

H の図形に関する妙な制約が効くのかと思いながらも直感を働かせると、左と下の壁から右と上の壁にかけていい感じに物を置くとよさそうな気がしてきました。

点a→点b の辺を、「点aとbのどちらにも物を置くとそれらの点の間は図形が通れない」という条件のとき張る、と決めると良さそうな気がしてきました。しかし、3つ以上の点が相互に影響しあい、結果的に非自明に図形をブロックする可能性も否定できませんでした。

「点aとbのどちらにも物を置くとそれらの点の間は図形が通れない」という条件は、「図形の1歩外側に点aを置くと、点bが図形の中に入ってしまう可能性がある」と同値なのではないかと感じました。

そうこうしているうちに Hemimor さんが G を通しました。この時点で1位でしたが、さらに完数を伸ばしました。すごいです！（1:42）

H の正当性は証明できませんでしたが、直感的に正しいと感じたため、とりあえず H の実装を始めました。実装の始めは最大流かと思いましたが、途中で実は最短経路問題（ダイクストラ）であることが判明しました。200行以上書き、案の定バグりもしましたが、サンプルが通るまでになりました。ここで、先ほどの「図形の1歩外側」は、斜め方向でも OK とエスパーしました。（そうでないと、サンプルが通らない）。しかし、結果は WA でした。このとき、8完が2チームも生まれてしまい、3 位に転落していました。しかも 8 完チームが解いたのはどちらも H 問題ではなく I 問題でした。（2:28）

H 問題は「解法が怪しすぎたしそりゃそうか」と思い、 I が簡単なら I を実装するほうがいいのではないかと思いましたが、I は解けていませんでした。WA の原因でありえるものとして「図形の1歩外側に点aを置いたとき、その図形自体がマス目の中に入っていないケースは無視する必要があるのではないか？」と思ったので、それを実装してみました。またバグりながらも修正し、正しそうな答えが出ました。残り時間ももう少しだし、駄目もとで提出してみたらなんと Correct Answer と出てびっくりしました。その後、そのまま通りました。（2:51）（ちなみに、そのとき緊張で提出の Send と間違えて一回 Reset ボタンを押してしまいました。）

このとき、前半のペナルティが軽いことが効いて 1 位に再浮上しました！その後は実装が軽い可能性がある I 問題を少し見ましたが、よく分からずコンテストが終了しました。

反省点

D 問題ですぐ印刷にいったことはよかったです。結局バグっている箇所は 4 個くらいありました。

H 問題は直感のままに行きましたが、証明できない部分があり最後までエスパーだったのは運ゲー感がありました。Bocchi The Tech が H 問題を完璧に示せていたらしいので、そのくらい強くなりたいです。

感想

noya さんは本番に強いです。Hemimor さんは考察力がすごく、本当に難しい問題を通すことが多々あります。自分は本番に弱いタイプでしたが、今回は多くのことが偶然噛み合って実力以上を発揮できたと思います。国内予選で優勝できるとは思っていなかったので感動しています。チームメンバーに感謝です。

また、ICPCスタッフ・東工大のスタッフ・優勝を祝ってくれた人たちにとても感謝です。12月に横浜大会があるので、楽しみです！playoffに出場できるように頑張ります。または……再度優勝します。