E869120's Blog

アルゴリズムや競技プログラミングに関する記事を書きます。

ICPC 2024 横浜大会参加記

1. はじめに

こんにちは、東京大学 4 年の米田 (E869120) です。

この度は、12/21-22 に横浜で実施された「ICPC 2024 横浜大会」にチーム Screenwalkers (E869120, square1001, Kodaman) で参加し、優勝しました。 そこで本稿では、参加記を記したいと思います。 9000 文字の長文となりますが、皆さんぜひお読みください。


2. ICPC のルール

最初に、日本における ICPC のルールについて簡単に説明します。日本では、原則として以下のような流れで選考が行われます。

  • 国内予選: 7 月にオンラインで実施され、約 400 チーム中 50 チーム程度が突破する。
  • 横浜大会: 12 月に横浜市で実施され、約 50 チーム中 10 チーム程度が突破する。
  • プレーオフ: 2 月にシンガポールで実施され、アジア太平洋地域から世界大会に進出するチームを決める。上位 20% 程度で世界大会に進めるが、横浜大会等で優勝した場合、プレーオフの結果にかかわらず世界大会に進める。
  • 世界大会: 世界から強豪 130 チームが集結し、競技プログラミングの世界一を決める。

ただし、まれに横浜大会以外の海外のコンテスト (台湾・韓国など) に参加するチームもおり、そこで優勝して世界大会進出を決めるというルートもあります。私達のチームも台湾の大会に参加しています (4 章を参照)。


3. 前座

まずは国内予選の話からしたいと思います。

2024 年 7 月 5 日、横浜大会への出場権を決める「ICPC 2024 国内予選」が実施されました。基本的には上位 50/400 チームが通るのですが、同校制限の都合上、東京大学では原則、トップ 10 に入らなければ通ることができません。もしトップ 10 に東大が 2 チーム以下しか入らなかった場合は 11 位以下でも通ることがあるのですが、ほとんどの場合 3 チーム以上入ってしまうので、きわめて稀です。

16 時 30 分、コンテストが始まります。見慣れない Mac の環境に手間取りながらも1、開始 11 分で最初の 3 問を通しました。その後、Kodaman が D 問題をバグらせながらも開始 43 分で通し、暫定 16 位です。この時点では想定の範囲内でした。しかし、プレッシャーがかかる状況下でのあまりの緊張から筆者が E 問題でとんでもない嘘解法を連発します。落ち着いて考えれば 30 秒で嘘解法と気付けるはずなのに、なぜか合っていると勘違いし、実装を始めてしまいました。実装も焦りのあまりバグらせサンプルが合いません。サンプルが合ったのが開始 1 時間 10 分頃でした。提出します。Wrong Answer。バグっているケースを探すと見つかったので、修正します。Wrong Answer。国内予選では問題数が少なく、誤答によるペナルティが非常に大きいので絶望します。嘘解法であることすら気づかないまま、コンテスト時間の半分となる 1 時間半が経過しました。さらに、square も焦りからか F 問題を詰め切ることができません。また、Kodaman が G 問題に挑戦しましたが、バグります。嘘解法であることにすら気づかない E 問題、解法が全く詰め切れない F 問題、バグの原因がわからない G 問題の 3 問の前に絶望します。順位表を見ると、10 位どころか 30 位にすら入っていません。1 位の可能性を期待されているチームが 50 位にすら入らなかったら歴史に残りそうだなあと思ったりします。2

残り時間は 80 分。切迫する時間を前に、このあたりで E 問題と F 問題の担当を交代し、ゼロから考え直します。すると、square が筆者の E 問題の解法が嘘であることに気づきました。また、筆者が F 問題の実装しやすい解法を思いつき、続いて square が E 問題のアイデアを思いつきました。しかし、残り 1 時間で 3 問通さなければならず、もし 3 問通せてもペナルティの関係3 で国内予選に落ちる可能性があるため、ほぼ 4 問通さなければならない絶望的状況でした。残り時間はわずか、焦りが頂点に達する中で筆者が F 問題を必死に実装し、入力例でバグらせながらも何とか正解します (2:15:07)。また、square も E 問題の見直した解法を実装して正解し (2:28:23)、Kodaman も G 問題のバグっているケースがわかりついに正解しました (2:36:50)。ここで長い間見ていなかった順位表を見ると 7 位で東大内 2 位。しかし、ペナルティがあまりにも重く、残り 20 分持ちこたえるかは微妙でした。

残り 20 分で 4 チームに抜かれるか、東大の 2 チームに抜かれれば全部終わり。数チームに解かれている I 問題を考えながら、なんとか持ちこたえることを祈っていました。日頃の行いが良ければ通り、そうでなければ落ちるとか、そんなバカなことを真面目に考えたりしていました。結果、I 問題は解法にたどり着きませんでしたが、東大のチームには 1 つも抜かれず、全体 11 位・東大内 2 位でギリギリの通過となりました。

通ったのはいいのですが、コンテスト後に「東大の恥だ」「日本の恥だ」と散々言われたどころか、何人かの人からの信用を失ってしまいました。なんて大変なことをしてしまったのだろう、と絶望しました。


4. 横浜大会までの練習

さて、横浜大会に向けて、以下のような課題がありました。

  • 大学の授業で忙しく、4 月の世界大会から競技プログラミングの問題をほとんど解いていなかった。個人の力をもう少し上げることはできるのではないか。
  • チーム力に大幅に改善できる部分があるのではないか。
  • メンタルが最大の課題ではないか。国内予選は 4 月の世界大会 (別のチーム Time Manipulators で出場) より明らかに緊張しており、世界大会銅メダリストとして参加するプレッシャーに完全に負けているのではないか。

そこで 9 月以降、毎週 1～3 回のチーム練習を行うだけでなく、個人練習も真剣に行い、チームの実力が少しずつですが上がっていきました。9 月下旬からは Universal Cup にも参加し、この順位も最初は 30～40 位くらいだったものが 10 位台に入れるようになりました。そして 11 月からは海外の ICPC のセットを解きまくりました。また、個人の力に関しても、筆者が Yandex Cup (権威ある競プロの個人戦) であと 2 人で海外オンサイト決勝、という成績を取るところまで行きました。

そこで 11 月中旬、私達のチームは台湾・台中市で開催された「ICPC2024 台湾大会」に参加しました。7 月の国内予選もあり、本番に弱いのではないかという話になっていたので、本番に慣れるという目的で参加しました。もちろん、国内予選のようなことが再び起こるのではないかという心配もありました。しかし、結果は Legendary Grandmaster 率いる強豪 std_abs を抑え優勝。東大の内部ルールの都合上、まだ世界大会進出は確定していなかったのですが、横浜で東大のチーム SPJ か HHIJKT が優勝しなければ世界大会進出、というきわめて心強い状況になりました。なお、台湾大会については以下の記事に詳しく書かれています。

そして、その後は ICPC 横浜大会に向けた調整を行いました。12 月は講演・出張授業や AtCoder Japan Open 決勝の作問作業と重なっており、あまりチーム練習ができなかったのですが、週に 1 回は必ずチーム練習を行いました。12/5 に行われた最後の対面での練習では、昨年の横浜大会の問題を解きました。その結果 4 時間半で全問正解、強豪 Speed Star と 20 分強の差で 2 位となり、今年の参加者と比較すると明らかに 1 位を取れる結果でした。これが横浜大会に向けた大きな自信になりました。

2 週間前からは、生活習慣の調整を行いました。4 年生の後期にもなると授業がほとんど存在しないため、当時の平均起床時刻が 9 時半とかになっていました。しかし、横浜大会は 9:15 にコンテストが始まり、少なくとも 7 時には起きる必要があります。そこで毎日 10 分ずつ起床時刻を早くする目標を立てました。結果、いろいろあって 7～8 分ずつしか早くなりませんでしたが、最後の数日で調整することができました。

最後の 1 週間は、練習しても緊張を増すだけなのでほとんど練習せず、形式的べき級数・マトロイド交差などのアルゴリズムの勉強をしていました。また、本番 1 週間前の 12/15 を最後に Twitter を休止しました。これは国内予選の反省を踏まえたことです (国内予選では、コンテストの前々日あたりにひどい悪口を言われて Twitter で炎上し、それがメンタル面で大幅に不利になってしまいました。負けの原因の 1 割くらいを占めると考えています)。

そして 12 月 21 日、ついに運命の日、ICPC2024 横浜大会当日がやってきました。


5. ICPC 2024 横浜大会参加記

1 日目 (12/21)

1 日目は 7 時半に起き、ライブラリの印刷を行いました。その後 10 時に自宅を出発し、横浜を少し観光してから昼食を食べ、コンテスト会場に向かいました。横浜ランドマークタワーの展望台から決戦の地・横浜の景色を眺め、本番への覚悟を決めました。

14 時から開会式が始まり、その後練習コンテストがありました。練習コンテストは 20 分で全問正解し、1 位となって良いスタートを切りました。練習コンテストの残りの時間では、タイピング練習とジャッジの計算速度の確認を行いました。その結果、手元とジャッジで最大 3.5 倍の差があることがわかり、参考になりました。その後、講演とチーム紹介が行われ、17 時半ごろに解散となりました。解散後は、横浜の中華街で夕食をとり、コンテスト会場から 2km 余り離れたホテルへと向かいました。

2 日目 (12/22)

その日は緊張であまり寝られず、午前 4 時半に目が覚めました。目が覚める前に、コンテストに関する夢を見ました。夢の内容は、私達のチーム Screenwalkers が凍結直前4 に中盤問題をすべて通し、凍結時点で 10 完となり 1 位、そして 2 位と 3 位が 9 完でライバルチーム SPJ が早解き 8 完で 4 位、という内容でした。凍結された時点で目が覚めたため、自分が最終的に勝ったかどうかを含め、それ以降の結末は知ることができませんでした。

チーム全体としては午前 7 時に起き、ホテルの朝食をたくさん食べました。その後、午前 8 時 15 分にタクシーでコンテスト会場に向かいました。ここで、タクシーを使うチームなど後にも先にも滅多にいないと思うのですが、これは 2 年前の横浜大会の反省があります。初日を熱で欠席した QCFium が競技当日に道に迷い、コンテストに遅刻するというハプニングがありました。結果的に、コンテスト開始 5 秒前に会場にたどり着いたため失格にはなりませんでしたが5、あと 5 秒遅れていれば失格となり、私達のチーム Time Manipulators ではなくライバルチームの KOMOREBI が世界大会に出ていたという綱渡りのような状況でした。

午前 8 時半、コンテスト会場に到着し、受付を済ませました。

午前 9 時、ほぼすべてのチームが会場に到着しました。

午前 9 時 10 分、すべてのチームがコンテスト会場に到着し、オープニングビデオが流れました。

そして 9 時 14 分、カウントダウンが始まります。あり得る結末は 3 通りで大差ない確率。SPJ などの東大の他のチームが優勝して世界大会進出を逃すか、他力で世界大会進出を決めるものの優勝を逃すか、それとも優勝して自力で世界大会進出を決めるか。果たして、国内予選 11 位からの大逆転勝利はあるのでしょうか。Screenwalkers の運命やいかに！

コンテスト序盤

午前 9 時 15 分、競技開始。最初は Kodaman がパソコンのセットアップを行い、筆者と square1001 が最初の 2 問を開始 8 分で正解。最初の 2 問以外は難易度がランダムなので、3 人で協力して簡単な問題を探す。K 問題と I 問題が簡単であることが判明。

その後、Kodaman が K 問題を実装して 1 ペナの末 34 分で正解、そして筆者が I 問題を開始 45 分で正解する。その間に、すでに解かれていた E 問題を square1001 に考察してもらい、開始 52 分で正解。この時点で square1001 は F 問題の解法がわかっていたので連続して実装 (ただし F 問題は実装が難しい)。

このタイミングで筆者が順位表を見ると C 問題が解かれていたので、Kodaman と一緒に考察し、F 問題と交代して筆者が実装、そして開始 1 時間 11 分で正解。簡単な 6 問を全チームの中で最も早く解き切り、順調な滑り出しとなった。


コンテスト中盤

続いて、Kodaman が G 問題で真ん中の 1 列を見て、左と右の個数の大小関係でゴールの位置が半分に絞れるという本質的なアイデアを提案。しかしこのアイデアだけでは残念ながらクエリ回数を超過してしまうので、筆者が考察を詰め、クエリ回数の 3 万回におさめることに成功。しかし、ちょうどそのあたりで square1001 が F 問題を提出するも Wrong Answer。

開始 1 時間 40 分時点で D 問題が解かれたため、Kodaman に考察してもらう。実は筆者も D 問題をその前に考察していたが、問題文の頂点番号の付け方のところを誤読してしまい、本来より難しい問題を考えてしまって解けず。しかし Kodaman は 10 分ほどで解法がわかり、D, F, G の 3 問を並行して実装する展開に。そして開始 2 時間 12 分で D 問題を正解。

G 問題についても、30 分ほどの格闘の末サンプルで正解したが、この問題は誤答を出しやすいインタラクティブ問題であるため、提出の前に慎重にランダムチェッカーを実装。ここで Wrong Answer のケースが見つかる。筆者はしばらく、これはプログラムのバグが原因だと思い込んでいたが、テストケースをよく見ると嘘解法であることが判明。1 列見るだけでは不十分で、実際には 2 列見る必要があった。なぜ考察の誤りに気づくことができなかったのだろうか。

そして F 問題と G 問題の 2 問で詰まる地獄のような展開になり、世界大会敗退を覚悟する。しかし、ICPC では国内予選というただ一つの例外を除き、ミスは許される。ICPC 横浜大会はミスをしても勝てる競技だ --- これはその時、筆者がチームに向けて言った言葉だ。

そうこうしているうちに L 問題が他のチームに解かれたので、わらにもすがるような気持ちで残った Kodaman に考察してもらう。すると、15 分ほどで解法がわかったと言う。ほぼ同時に square1001 が解いていた F 問題がついに正解となったため (3:13)、Kodaman が L 問題を実装、1 ペナの末正解 (3:28)。2 問を同時に間違える難局の中、Kodaman には本当に助けられた。Kodaman がいなければ 10 完どころか 8 完や 9 完で終わっていた可能性もあっただろう。

そして筆者も、他の 2 人が実装していた 40 分ほどの時間を使って G 問題の解法を、実装方針の部分まで詰めることができた。10 分余りで実装を修正する。

このタイミングで順位表を見ると以下の通りであった。

　1位　Screenwalkers　9問807分
　2位　Penguin Feeders　9問813分

わずか 6 分の差である。それに対して、1 回 Wrong Answer を出したときのペナルティは 20 分。既に何回もミスを数えている以上、優勝のためにはもうミスは許されない。サンプルで正解した後も、既に実装済みのランダムチェッカーで 10 万ケースを試す、そして変数のミスなどを目視で確認するなど、ここ数年で一度も経験してないレベルで慎重にプログラムの間違いを確認する。

10 分後、ついに提出する。開始 3 時間 52 分、ついに Correct という文字列が表示され、10 完。世界大会進出が確率 99% の勝勢となり、優勝も濃厚になる。チームで喜びを分かち合う。


コンテスト終盤

しかし、私達にはまだ解ける問題が残っていた。私が実装していた 20 分強の時間を使って square1001 と Kodaman が J 問題を協力して考察し、square1001 が本質的なアイデアを出してほとんど解法にたどり着いていたのだ。

10 完した後すぐに square1001 が実装を始める。まずは実数の場合を実装し、サンプルが合ったので有理数の場合を実装。2 回の Wrong Answer を出すも、チェッカーを書くなどしてバグを探し、10 分を残して正解。これで 11 問正解となり、完数差をつけての優勝が決まった。

なお、残るわずかな時間で筆者が H 問題の通りそうな解法6 を実装したが、間に合わずに終了した。


6. おわりに

今回は優勝という結果に終わりましたが、他の 2 人のチームメンバーが 8 割くらいの部分をやっていました。Kodaman は 2 人が同時にバグらせる難局の中 D 問題と L 問題を 1 人で通し、square は難問の F 問題と J 問題を解いてくれました。今回の横浜大会は、主に 2 人のおかげで優勝という結果になったと思います。

一方、筆者は G 問題で他の人の解法のミスに気付かないなど、今回は中盤以降あまり貢献することができませんでした (この問題は他のほとんどの上位チームも苦戦しているので、もしかしたら G 問題を解いた者の宿命かもしれませんが… そう考えると多少は貢献できているのかもしれません)。

横浜大会 1 つですべてのことが言えるわけではありませんが、いまチームの中で最も実力が足りてないのは自分だと思います。世界大会でメダルを取るために、より一層精進してまいりますので、応援よろしくお願いします。

  1. 東大では、浅野キャンパスの情報教育棟から参加することになっており、ここでは普段使っていない Mac が採用されている。↩
  2. 競技中は確認していなかったが、一時 42 位まで落ちていたらしい。↩
  3. ICPC では正解時間の累積がペナルティになるため、後半に問題をたくさん通すとペナルティ上きわめて不利になる。たとえば、開始 30, 60, 180 分で 3 問を通した場合のペナルティは 30+60+180=270 分、開始 80, 90, 110 分に 3 問を通した場合のペナルティは 80+90+110=280 分となり、後者の方が最後に解いた時刻が早いにもかかわらず不利になる。↩
  4. ICPC では、残り 1 時間となった時点で順位表の更新が止まる。これを「順位表の凍結」という。↩
  5. その翌年から ICPC の運用が厳しくなり、決められた時間 (コンテスト開始 10-20 分前) に到着しなければ失格となるようになりました。来年以降出場する人は注意しましょう。↩
  6. 適当に増加路っぽいものを見つけて改善を繰り返すアイデア。盤面の大きさの 1.5 乗で通りそうな解法を実装したが、コンテスト終了後に AOJ に提出したところ非自明な反例があって Wrong Answer となった。僕の方針だと実際は 2 乗か 3 乗必要な気がしている。↩