1. はじめに
こんにちは、お久しぶりです。東京大学 4 年の米田 (E869120) です。 この度は、11/16-17 に台湾・台中市で行われた競技プログラミングの大会「ICPC Taichung Regional 2024」にチーム Screenwalkers (E869120, square1001, Kodaman) で参加し、優勝しました。
さて、私は、コンテストに参加した選手として、大会でどのようなことがあったか、そして ICPC の楽しさと感動を社会に伝えていくことは重要な責任の一つだと考えています。 そのため、今回は参加記を執筆させていただきたいと思います。
1 万字の長文になりますが、皆さんぜひお読みください。
2. ICPC とは
まずは ICPC について簡単に説明させていただきます。 ICPC は大学生・大学院生を対象とした競技プログラミングの大会ですが、通常の AtCoder とは異なり、3 人 1 組のチーム戦形式で行われます。
また、チーム戦とは言ってもパソコンが 1 台しかないため、同時に 1 人しかプログラムを書くことが出来ません。したがって、他の 2 人がどのようなことをやるかを含め、戦略要素も重要になってきます。
ICPC では、大きく分けて国内予選・アジア地区予選・世界大会の 3 つがあり、それぞれ以下のようになります。
- 国内予選: 日本から 400 チーム程度が参加し、40 チーム程度が合格する。
- アジア地区予選: (一部例外はあるが) 国内予選を突破したチームが参加し、日本からは 5 チーム程度が合格する。
- 世界大会: 世界から集まった強豪 150 チーム程度が参加する。
しかし、アジア地区予選については、同じ大学から 1 チームしか参加できないなどの複雑なルールがあるため、以下の項で詳しく説明させていただきます。
2-1. アジア地区予選のルール
アジア地区予選は、アジア太平洋地域 (日本・韓国・台湾など / 中国は含まれない) において世界大会進出チームを決めるためのコンテストであり、サッカーでいう「アジア最終予選」に相当します。今年は、アジア地区予選として以下の 5 つの大会が実施されます。
| 大会 | 時期 | 参加チーム数 |
|---|---|---|
| 台湾大会 | 11/16-17 | 110 前後 |
| 韓国大会 | 11/22-23 | 80 前後 |
| インドネシア大会 | 11/30-12/1 | 100 前後 |
| ベトナム大会 | 12/12-13 | 130 前後 |
| 日本大会 (横浜で開催) | 12/21-22 | 50 前後 |
国内予選を突破した日本のチームは、12/21-22 に横浜で実施される日本大会と、他の 4 つのうちどれか 1 つ、の合計 2 回に参加することができます。なお、海外の大会に参加する場合、海外出張の費用が自己負担になるなどの都合もあり、多くの日本チームは日本大会だけに参加するのですが、私達のチームは台湾大会と日本大会の 2 つに参加しています。
ここで、どれか 1 つの大会で優勝すると、世界大会の進出が確定します。また、仮に優勝できなくても、どれか 1 つの大会で上位 20% 程度の成績を残すと、2 月下旬に実施されるプレーオフに進出することができ、そしてそのプレーオフでも上位 20% 程度の成績を残すと、世界大会の進出が確定します。つまり、世界大会進出への道は下図のようになります。
しかし、ICPC には同じ大学からは 1 チームしか世界大会に進出できないという絶対条件があります。そこで東京大学では、「もし複数の東京大学のチームが Regional で優勝した場合、日本大会で優勝した方の勝ちとする」という横浜優先ルールを採用しています。
そのため、もし自分のチームが台湾大会で優勝しても、東京大学の他のチームが日本大会で優勝した場合、自分のチームの世界大会への切符は無くなってしまいます。
2-2. 競技のルール
続いて、ICPC の競技ルールについて説明させていただきます。まず、ICPC では 10 問から 15 問程度の問題が出題され、これらの問題を 5 時間で解くという形式になっています。選手は最初の 4 時間のみリアルタイムの順位表を見ることができ、4 時間以降は開始 4 時間時点での順位表と、4 時間以降の各チームの提出回数のみ見ることができます。
順位付けについては、部分点はなく、より多くの問題を解いたチームが上位という方式を採用しています。しかし同点の場合、以下のように定義されるペナルティの大きさによって順位が決まります。
- 解くのにかかった時間の合計。
- ただし、誤答プログラムを提出した後に正解した場合、1 回の誤答につき 20 分が加算される。
たとえば、コンテストが 9 時に始まり、あるチームが 9 時 20 分に A 問題、9 時 30 分に B 問題、9 時 50 分に C 問題を誤答なしで正解したとします。このとき、ペナルティは 20+30+50=100 分になります。
また、別のチームが 9 時 10 分に A 問題を誤答なしで正解し、9 時 40 分に B 問題を 3 回の誤答の末に正解したとします。このとき、ペナルティは (10+40)+20*3=110 分となります。なお、もしその後このチームが C 問題に誤答の提出をしていたとしても、最終的に正解に至らなかった場合、ペナルティは加算されません。
3. 私達のチームの紹介
ICPC のルールについてお分かりいただけたところで、私達のチーム Screenwalkers について紹介させていただきたいと思います。
Screenwalkers は今年 6 月に結成したチームであり、以下の 3 人のメンバーからなります。なお、ICPC は AtCoder と全く異なる競技なのでそれほど大きい意味はありませんが、AtCoder での直近の 3 人のパフォーマンスは平均して 2600 から 2900 前後です。
E869120
筆者。学部 4 年。国際情報オリンピックでの金メダル獲得、今年 4 月に実施された ICPC 世界大会での銅メダル獲得など、3 人の中で最も経験豊富。著書に競技プログラミングの鉄則 など 3 冊があり、世界合計約 9 万部のベストセラーになっている。
square1001
E869120 の双子の兄。学部 4 年。今年 4 月の世界大会では筆者と同じチーム Time Manipulators に所属し銅メダルを獲得。おそらく 3 人の中で最も考察力に優れているが、実装もあまりバグらせない。ヒューリスティック系のコンテストでは最強。
Kodaman
学部 1 年。今年から ICPC に出場する期待の新人。2023 年まで中高生向けの大会「国際情報オリンピック」に参加し 3 回の金メダルを獲得するなどの圧倒的な実績を持つ。3 人の中で最も実装力に優れている。
4. 台湾大会のライバルチームの紹介
前章のチーム Screenwalkers の説明を読んで、これは強い、優勝間違いなしと思った方もいるかもしれません。しかし、台湾大会に参加するチームも強く、今年の台湾大会はここ数年で最も厳しい争いになると予想されていました。本章では、強いチームをいくつか紹介させていただきます。
PCkomachi
今年の台湾の国内予選で優勝したチーム。CodeForces 赤 2 人、橙 1 人からなる。AtCoder や CodeForces の実力的には Screenwalkers の方がやや分が良いが、ICPC 系の大会では強く、国内予選・アジア地区予選の 2 連覇を十分狙える強豪である。
std_abs
台湾史上最強と言われているチームの 1 つである。チームメンバーの 1 人である BurnedChicken は、CodeForces で Legendary Grandmaster の称号を持ち、一時はレーティング 3200 (世界ランク 20 位前後) を突破していた。また、他の 2 人のメンバーも CodeForces 赤である。国内予選では PCkomachi に敗れたが、実力的には最強だ。
5. なぜ台湾に参加したか
しかし、なぜ私のチームは台湾に参加したのでしょうか。
まず、台湾・韓国・インドネシア・ベトナムのうち、チームメンバー全員の日程が合うのは台湾とベトナムのみであったため、その 2 つのうち片方に参加することに決めました (ルール上両方参加することはできない)。一方、その 2 つの中では結構迷いました。
そこで、実際に台湾大会の国内予選を解き、もし優勝相当の結果を出せたら台湾、優勝できなかったらベトナム、ということに決めました。すると、本番全問正解がいなかったところラスト 5 分で全問正解となり、優勝相当の結果となりました。これが台湾への参加の決め手となりました。
6. 参加記本編
それでは、いよいよ ICPC 2024 台湾大会の参加記に入りたいと思います。
11/14
台湾大会は 11/16 から始まるのですが、当日のコンディションを第一に考え、私達のチームは前々日入りすることになりました。17 時頃に成田空港に集合し、19 時 40 分成田発、22 時 45 分台北着のチャイナエアライン 109 便に乗りました。機内食も美味しく、座席も快適でした。
台北に着いた後は、夜も遅いので空港近くの Novotel Taipei Taoyuan International Airport に宿泊しました。空港近くの大手のホテルにもかかわらず 1 泊 1 万円程度しかしなかったので、日本よりは圧倒的に安いです。
11/15
その日は観光をしました。午前 10 時頃にホテルを出発し、台北 101 展望台に登りました。その後、スケジュール上は故宮博物院などに行く予定だったのですが、台風 25 号が近づいており台中に移動できるか不安だったので、14 時頃に予定を切り上げ、14 時 21 分発の台湾新幹線で台中に向かいました。15 時半頃には台中に着きました。
11/16
その日は開会式と実機演習がありました。14 時に開会式が始まり、競技ルールの説明等が行われた後、実際のコンテストサイトに慣れるための実機演習が 15 時 15 分に始まりました。
実機演習は今年の台湾の国内予選を 1 時間で解くという形式のものでした。台湾の国内予選は 2022 年のものしか解いておらず、2024 年のものを解いていなかったため初見でしたが、なんとか 6 問正解で 1 位を獲得することが出来ました (しかし、多くの台湾のチームは真面目に取り組んでいなかったので 1 位を取れなかったら失敗と言っても良い)。
なお、実機演習では問題文が配布されず、1 台しかないコンピュータで問題文を読まなければならなかったので、本番も問題文配布無しだったらどうしようと思っていたのですが、明日は配布されるというアナウンスがあり、安心しました。
11/17
早いもので、いよいよ競技日です。
私達のチームのホテルは台中駅 (日本でいう大阪駅のようなもの) 付近でしたが、競技会場に行くには新幹線の台中駅 (日本で言う新大阪駅のようなもの) にまず移動し、そこから出る午前 7 時 40 分発のシャトルバスに乗る必要があります。そのため、私達は 6 時 15 分に起床し、6 時 40 分頃の電車に乗りました。
ここで、新幹線の台中駅は普通列車の「新烏日駅」に対応するのですが、その新烏日駅の次の駅の名前が「成功駅」だったので、次 (ICPC 台湾大会本番) は成功しかない、という話をチームメンバーとしたりしていました。縁起が良い。
その後、新幹線の台中駅で朝食をとり、シャトルバスで競技会場に向かいました。8 時 30 分頃に受付が終わり、コンテストホールに入場。
ここからの 1 時間は緊張でした。コンテストホールは体育館のようなところで、そこに国内予選を勝ち抜いた 110 チームが集まっているわけですから、緊張しないわけありません。
ちなみに競技開始 15 分前くらいに、チームメイトに「今どんな気分か？」と聞かれたので、「ジェットコースターに乗る前のような気分だ」と答え、「何メートルくらいか」と聞かれたので「150 メートル」と答えたのを覚えています。なお、後で調べたところ、世界に 150 メートルのジェットコースターはほとんどありませんでした。
競技開始 5 分前、コンテストシステムにログインしました。競技開始 1 分前、戦略に関する最後の話し合いを行いました。そして競技開始 10 秒前、カウントダウンが始まりました。果たして、どのような展開になるのでしょうか。台湾のチームが勝利するのでしょうか。それとも、奇跡が起こるのでしょうか。Screenwalkers の運命やいかに！
コンテスト序盤 (1)
午前 9 時 30 分、コンテストが始まりました。問題は A 問題から N 問題の 14 問。問題は難易度順ではなく、ランダムな順番になっています。
最初は筆者がエディタのセットアップ等を行い、square1001 が最初の A 問題から、Kodaman が最後の N 問題から読みました。すると開始 1 分、A 問題が簡単であることが判明したため、square1001 が実装。開始 2 分で正解しました。
続いて、E869120 が E 問題を読み、それも簡単であることが判明したため、実装。開始 7 分で正解しました。この時点で B が解かれていたので筆者が読むも、コンテスト序盤の緊張で読解に 4 分ほど消費。しかし開始 13 分で B 問題を正解。そして開始 17 分、square1001 がまだ解かれていなかった C 問題を正解しました。
その後は square1001 が D 問題の解法を思いつき、Kodaman が M 問題の解法を思いつきました。D 問題は既に解かれており、M 問題はまだ解かれていませんでしたが、パソコンが 1 台しかないのに実装量が重いということで後回しにすることになり、Kodaman が M 問題を先に実装しました。すると開始 31 分、M 問題を正解。
続いて、Kodaman の実装中に H 問題の解法を思いついた筆者が H 問題の実装に挑戦し、開始 36 分で正解。そして後回しにしていた D 問題を square1001 が実装し、開始 45 分で正解しました。それで一番簡単な 7 問を正解し、順位表は以下のようになりました。
1位 Screenwalkers 7問171分
2位 std_abs 6問104分
しかし、std_abs は開始 47 分で 7 問目を正解し、Screenwalkers は抜かれる展開となりました。
1位 std_abs 7問151分
2位 Screenwalkers 7問171分
コンテスト序盤 (2)
その後、筆者が F 問題の解法を思いつき、急いで実装しました。実装 100 行程度のやや難しい問題であったため少しバグらせましたが、開始 1 時間 5 分で正解、再び 1 位に返り咲きます。しかし、std_abs も後を追うように開始 1 時間 8 分で正解。なかなか抜かせません。
1位 std_abs 8問219分
2位 Screenwalkers 8問236分
続いて、E869120 の実装中に square1001 が I 問題の解法を思いついたため、誰が実装するかという話になりましたが、このようなデータ構造系の問題は Kodaman の方が実装が得意ということで Kodaman が実装することになりました。開始 1 時間 40 分、ようやく正解します。しかし順位表を見ると、std_abs は既に 1 時間 23 分時点でこの問題を解いていました！
1位 std_abs 9問302分
2位 Screenwalkers 9問336分
自分も大きなミスはしていないはずなのに、解いても解いても抜かせない。悪いたとえですが、公道を時速 300 キロで走っているのに抜かれてしまうような感覚がしました。そうして、やや不利な状態で中盤を迎えることになりました。なお、後で分かったことですが、このコンテストは 9 問目と 10 問目の間に大きな難易度の差があります。
コンテスト中盤 (1)
しかし、コンテスト中盤、転機が訪れます。まず、Kodaman の実装中に筆者が K 問題のアイデアだけ思いついていたので square1001 に共有。その後、square1001 が解法の細かい部分の考察と証明を行い、その後実装に挑戦しました。その結果、2 時間 3 分で一発で正解。
また、Kodaman が最初苦戦していた J 問題の最初のアイデアを square1001 が思いつき、Kodaman が I 問題を正解した後にアイデアを共有。すると開始 2 時間頃、Kodaman がついに解法を思いつき、実装に挑戦しました。流石の実装力、ほぼバグらせずに 2 時間 21 分で一発で正解。その結果、中盤の早い段階で難しい 2 問を正解し、一気に優勢になりました。
1位 Screenwalkers 11問600分
2位 std_abs 9問302分
しかし、コンテストはまだ半分しか終わっておらず、まだ勝負がついたわけではありません。勝率 80% 程度の感覚です。
コンテスト中盤 (2)
その後、筆者が N 問題の解法の本質的なアイデアを思いついたため、square1001 に証明を投げます。5 分後、証明ができたと返ってきました。また、ほぼ同時に square1001 が L 問題の解法を思いつき、筆者が N 問題の解法を思いついたため、L 問題と N 問題を交互に実装することになりました。
しかし開始 3 時間頃、N 問題の解法が TLE (実行時間制限超過) になる可能性が高いことに気付きました。この問題の制約は N が 10 万以下なのですが、計算量が O(N^{1.5} * log N) であり、定数倍も悪いです。そこで一旦解法を見直し、実装権を L 問題に渡すことにしました。
だが、残念ながら L 問題も上手くいきません。開始 3 時間 13 分、L 問題の実装が終わり提出したものの、TLE (実行時間制限超過)。定数倍の差だと思っていたので枝刈りを試すも、今度は WA (不正解) となってしまいました。
そこで square1001, Kodaman を含めた 3 人で協力して N 問題の log を減らす方法について考察しました。すると、square1001 が本質的なアイデアを思いつき、筆者がそれを詰めたところなんと解法が分かりました。そうして筆者が N 問題の実装に再び挑戦することになりました。
コンテスト終盤 (1)
筆者が実装に挑戦した N 問題ですが、実装を始めたタイミングでは 15 分で終わると思っており、4 時間の凍結前に N 問題を通して 12 問正解にすることを目指していました。
しかし、コードを書いても書いても全然書き終わりません。時間が経つにつれ、思ったより難易度が高いことが明らかになります。また、開始 3 時間 28 分、std_abs が J 問題を正解し、またこれまでに L 問題を正解していたことから、追いつかれてしまいます。
1位 Screenwalkers 11問600分
2位 std_abs 11問703分
急いで実装を進めますが、これは逆転負けになってしまうのではないかという感覚が出てきます。正確な時刻は覚えていませんが開始 3 時間 45 分頃、ようやく最後の高速化を除いた部分の実装が終わりました。しかし、入力例 1 が合いません。
既に 180 行の巨大なプログラムをにらみ、ブレークポインタも活用してどこで間違っているのかを考えます。すると入力例 1 が合いましたが、入力例 2 が合いません。バグの原因を頭から繰り出して考察すると、場合分けを忘れていたことが判明します。入力例 2 が合いました。しかしちょうどその頃、開始 4 時間となり、順位表が凍結されたというアナウンスが流れました。
E869120 の実装中に Kodaman が G 問題の解法を思いついたため、実装者以外の 2 人が今後の戦略について話し合いました。その結果、全問正解を狙うのはリスクがあり、N 問題と L 問題に集中したほうが良いという結論になりました。また、開始 4 時間 10 分時点で N の実装が終わらなかった場合はプログラムを印刷の上、L に実装権を交代することを決めました。
しかし、もう遅いのか。もし N 問題が失敗に終わった場合、戦略を切り替えて L 問題を通しても負ける可能性があります。たとえばライバルチームの std_abs が 12 問目を 4 時間 5 分で正解し、自分が 4 時間 50 分でプラス 1 回の誤答で正解したとします。すると、L 問題は既に 2 回の誤答を出しているため、以下のように負けてしまいます。
1位 std_abs 12問948分
2位 Screenwalkers 12問950分
既に自分は、N 問題が全問題の中で最難で、選ぶ問題を間違えたと感づいていました (後で分かったことですが、この予測は正しく、実際に N 問題は最も難しい問題です)。しかし、そのミスを取り返すことができるかが勝敗を左右すると言っても過言ではないことも分かっていました。
1 分に 15 行から 17 行のペースで、残りの高速化を実装します。実装量は 180 行から 262 行に増えましたが、開始 4 時間 6 分、入力例に正解し、提出します。しかし予想通り不正解が返ってきます。
その後、プログラムを印刷の上、実装権を L 問題に交代することになりました。筆者は印刷したプログラムを必死にデバッグします。しかしプログラムは 262 行、その中でも複雑です。こんなのがデバッグできる訳ないと思っていたので、チームメンバーにひたすら「解けなくてすみません」と言ってた覚えがあります。
だが、プログラムを頭から読んでいくと、25 行目から 30 行目のあたりで自分のミスに気付きます。処理を 1 行入れ忘れていたのです。実装権を交代し、ミスと思われるところを修正し、開始 4 時間 9 分、提出します。もちろん、その他にもバグがあると思っていたので、不正解だろうと思っていました。しかし、結果が出ません。不正解の場合はすぐに結果が出るので、もしかしたらと希望が出てきました。そして 1 分後、画面に表示された文字は CORRECT でした。
泣きました。
競プロの大会で久しぶりに涙が出ました。本当に解けて良かった。
コンテスト終盤 (2)
ここで初めて、Screenwalkers は勝勢といえる状況になりました。しかし、もし std_abs が凍結後に 2 問正解して 13 問正解になると負ける状況であり、まだ勝率 95% という感覚でした。残りのすべては L 問題にかかっています。
L 問題は、三分探索を黄金分割探索に変えることで定数倍高速化する、という方針で square1001 が実装していました。しかし開始 4 時間 20 分、バグが取れません。そこでコードを印刷し、黄金分割探索の実装に慣れている Kodaman に実装してもらうことにしました。すると、バグとの格闘の末、開始 4 時間 37 分でようやく入力例が合い、提出します。
すると 1 分後、CORRECT という文字が表示され、私達は 13 問正解でついに勝利を決めることができました。コンテスト終了後、チームの全員で喜びを分かち合いました。チームの 3 人全員が活躍した、誰が欠けていても 11 問正解で終わっていて優勝できなかった、そういう試合でした。
(なお、G 問題は残り少ない時間で square1001 が実装に挑戦しましたが、間に合いませんでした。)
11/18
私達のチームは、晴れて優勝という結果で帰国することができました。8 時半にホテルを出発し、12 時 35 分台北発、16 時 35 分成田着のチャイナエアライン 104 便に乗り、帰国しました。優勝トロフィーを持って帰るのが大変でしたが、何とかなりました。
7. おわりに
最後までお読みいただきありがとうございました。11000 文字を 2 時間半で執筆したため、かなり駄文になってしまったことをお詫び申し上げます。
今回の台湾大会は優勝という結果に終わりましたが、まだ世界大会進出は確定していません。12/21 の日本大会で他の東大チームが優勝した場合、予選敗退となってしまいます。そして東大には、他にも私達と互角くらいのチームがおり、負ける可能性があります。
もちろん、2 章でも記した通り、東工大・京大・阪大・筑波大など他の大学のチームが日本大会で優勝すれば、私達はたとえ最下位でも世界大会に進出できます。しかし、できれば東大の他のチームに勝って自力進出を狙いたいという考えています。
最後になりますが、横浜大会はわずか 3 週間後に控えています。皆さん是非、チーム Screenwalkers を応援よろしくお願いします。
