E869120's Blog

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

ICPC 2023 世界大会参加記

1. はじめに

こんにちは、東京大学 4 年の米田 (E869120) です。この度は、4/14～19 にエジプトで開催されたプログラミングコンテスト「ICPC 2023 世界大会」に、チーム Time Manipulators (E869120 + square1001 + QCFium) として参加し、世界 9 位で銅メダルを獲得しました。

そこで本記事では、ICPC について、ICPC に向けた練習について、そして本番の参加記について記したいと思います。長文になりますが、ぜひお読みいただけると幸いです。


2. ICPC について

まず、読者の中には ICPC を知らないという方もいると思うので、「ICPC が一体どういうものか」という話から始めましょう。

ICPC は、大学生・大学院生を対象としたプログラミングの大会です。ここで、プログラミングの大会にも様々なものがありますが、ICPC はウェブサービスやアプリを作成するようなハッカソンのようなものとは異なり、制限時間内にプログラミングの問題をできるだけ多く解く大会です。いわゆる数学の試験のプログラミング版、と思っておくと分かりやすいと思います。

ICPC で出題される問題

それでは、ICPC ではどのような問題が出題されるのでしょうか。過去に出題された問題の例1として、以下の問題を考えてみましょう。

  • あるクラスの友達関係のデータが与えられる。
  • これから、友達関係でプレゼント交換を行う。プレゼント交換は、それぞれの友達についてプレゼントを渡す向きを決め、一方がもう一方にプレゼントを渡すという形式で行われる。
  • 不公平感をなくすため、各生徒がもらえるプレゼントの数の最大値と最小値の差をできるだけ小さくしたい。このような方法を 1 つ出力せよ。
  • たとえば友達関係が下図左側のようなものである場合、下図右側のように向きを決めれば差を 0 個にできる。

この問題を解く最も簡単な方法は、あり得る方法をすべて調べ上げることです。

たとえば上図の例の場合、プレゼントの向きの決め方としては 2 の 5 乗通り、すなわち 32 通りがあります。これらを全部調べて最も差が小さかったものを出力すれば、正しい答えを出すことができます。

しかし、この方法は友達関係の数が増えると上手くいきません。たとえば友達関係が 50 個ある場合、1000 兆通り以上の方法を調べ上げる必要があり、現代の PC を以てしても実行に数日以上かかってしまいます。そして、この問題では最大 3000 個の友達関係が与えられることがあるため、残念ながら正解することができません。

そこで「ある工夫した解法2」を使うと、3000 個の友達関係であっても 1 秒以内に答えを出せるようになります。このように ICPC では、プログラムを実装する力だけでなく、高速に答えを出せるような工夫した解法を考える能力 も重要になります。


大会の流れ

次に、ICPC がどのような流れで行われるかを説明します。まず、ICPC は 3 人 1 組のチーム戦／ただし同時にプログラムを実装できるのは 1 人 という形式で行われます。個人戦と異なり、戦略やチームワークも非常に重要です。たとえば実装者以外の 2 人をどう有効活用するかなどが重要になります。

また、日本の ICPC は一次予選・二次予選・世界大会の 3 つのステージからなり、それぞれ以下のような流れになっています。

大会 概要 競技時間 倍率
一次予選 オンラインで開催される 3 時間 300 チーム → 40 チーム
二次予選 横浜で開催される 5 時間 40 チーム → 2～4 チーム
世界大会 毎年開催国が異なる 5 時間 世界各地から 130 チームが参加

ここで世界大会では約 130 チームが参加しますが、そのうち上位 12 チームには以下のようにメダルと賞金が授与されます。ICPC は世界で最も権威のある大会の 1 つなので、ICPC でメダルをとることは多くの競技プログラマーの夢になっています。

大会 順位 チームの賞金
金メダル 1 位 約 250 万円
金メダル 2～4 位 約 120 万円
銀メダル 5～8 位 約 90 万円
銅メダル 9～12 位 約 50 万円

ICPC については理解できましたでしょうか。それではいよいよ、本編である ICPC 2023 世界大会の参加記に移りたいと思います。


3. ICPC 2023 参加記：世界大会までの過程

まずは世界大会に出場するまでどのような練習を行ったか、手短に記したいと思います。

2022 年 6 月

2022 年 6 月 15 日、当時東京大学 2 年の E869120、当時東京大学 2 年の square1001、当時東京大学 1 年の QCFium の 3 人でチームを組み、チーム「Time Manipulators」が結成しました。

2022 年 7 月

7 月上旬に一次予選が開催されるため、オンラインで一次予選の過去問を解くなどの練習を行いました。その結果、国内予選では 2 位で通過しました。

2022 年 11 月

12 月下旬に開催される二次予選に向けた練習を開始しました。チームで東大に集まって過去問を解いたり、戦略を立てたりしました。

ここで 1 つ記しておかなければならないことは、私達のチームにとって戦略とチームワークが非常に重要であるということです。私達のチームメンバーは全員、国内最大級のコンテストサイト AtCoder において国内 50 位程度の実力があるのですが、他の出場チームのうち、国内トップ 20 に入る実力者がいるチームが 4 チームほどあります。つまり、私達のチームが世界大会への切符をつかむには、実力の分を戦略とチームワークで補わなければなりません。そのため、戦略に関しては毎回の練習ごとに詳細な分析を行うなど、かなり力を入れて考えました。

2022 年 12 月

そして 12 月 28 日、二次予選を迎えました。10 日前にチームメンバーの 1 人がコロナに感染したり、前日に別のメンバーが熱を出したりするなどのトラブルが起こりましたが、何とか 2 位で世界大会進出を果たしました。

2023 年 2～7 月

当時、世界大会は 2023 年 11 月に予定されていたため、この時期はあまり多くの練習を行わず、「高校数学の基礎が 150 分でわかる本」の執筆作業に注力していました。7 月 26 日に発売され、2 万部以上売れました。

2023 年 9～10 月

世界大会の 2 か月前になり、いよいよ世界大会に向けた練習を始めました。1 日平均 5 時間の個人練習に加え、チームで東大に集まって海外の ICPC 予選の過去問を解くなどの練習を行いました。その結果、世界大会の 3 週間前の時点ではいよいよ完成度が上がり、メダルを狙える予感がしてきました。

ところが、10 月 28 日、戦争の影響で ICPC 世界大会が無期限で延期されるという一通のメールが来ました。あと 4 日大学に登校すれば世界大会というタイミングでした。これまでの努力が無駄になってしまうかもしれないという絶望感と、戦争は絶対に許されないという強い思いを同時に感じました。

2023 年 11～12 月

ICPC が延期され、最終的には中止も懸念されるような状況であったため、ICPC の練習を行えるような状況ではありませんでした。

2024 年 1 月

あれから 3 ヶ月が経った 1 月 16 日のことです。ICPC の開催可否に関する連絡が日本時間の 1/20 午前中に来るという連絡がありました。そして迎えた 1 月 20 日、午前 8 時に起きてメールを確認しました。まだ来ていません。9 時にももう 1 回メールを確認しました。まだ来ていません。その後、3 分おきくらいにメールを確認しました。10 時になっても来ません。中止になるのではないか、あるいは日程が他の重要な学業イベントと重なって出場できないのではないかと不安が高まります。しかし 10 時 16 分、ICPC 世界大会がエジプトで 4/14～19 に開催されるというメールが送られました。この時は本当に嬉しかったです。

2024 年 2 月下旬 (50 日前)

大学の期末試験が終わり、いよいよ本当の世界大会に向けた練習が始まりました。最初にやったことは、2/17～25 に開催された Osijek Programming Camp に参加したことでした。チームで東大に集まり、7 日間練習を行いました。

最初の方はあまり良い結果が出ず、10 月との落差に絶望しました。9 月 10 月の調整がたまたま上手くいっただけで、今回はチームの完成度を上げられないのではないかと不安を感じました。しかし最終日には 7 日間で最高の結果を出すことができました。

その後、チームとしての目標を決めました。チームとしては、コンテストで出来るだけ高い成績を残すことを第一の目標とするが、できれば 12 位以内のメダル獲得を目指す という目標を設定することになりました。3

2024 年 3 月上旬 (40 日前)

その後、10 月の練習と同様、チームで東大に集まって海外の ICPC の予選を解くなどの練習を行いました。チーム練習は週 2 回程度行い、練習がない日は 1 日 10 時間程度の個人練習を行いました。当時、パソコンが同時に 1 台しかない影響で実装速度がボトルネックになっていたため、実装力を上げる練習を中心に行いました。

また、戦略に関してもこの時期に深く考えました。2022 年 12 月の二次予選よりもさらに上のレベルのものを目指して考えました。戦略は序盤・中盤・終盤の 3 つの段階に分けて考え、どういう条件だったらこのような戦略を取る、などの場合分けを含めて考えました。戦略に関しては機密情報なのですべてを教えることはできませんが、一部の例として、以下のような戦略があります。

序盤戦略の例

  • 難易度順に並んでいない問題が 12 問あるとして、普通は最初 1 人 4 問ずつに担当を分けるところ、英語が読むのが早い square1001 が 6 問、その他のメンバーが 3 問を担当するように分ける。
  • その後、square1001 が最初の 5 分で 6 問の問題ジャンルを把握し、その中で他の 2 人が得意そうな 2～3 問を該当者に渡す。

終盤戦略の例

  • 終盤は、3 対 3 戦略・3 対 2 戦略 A・3 対 2 戦略 B・3 対 1 戦略のいずれかを適用する。
  • 詳しくは書かないが、どれにするかは残り時間や順位表等に応じてほぼ機械的に決める。
    • 3 対 3 戦略は、1 人が 1 問に取り掛かり、追加で 3 問解くことを目指す戦略である。
    • 3 対 2 戦略 A は、1 人が 1 問、残り 2 人が別の 1 問を協力して解く戦略である。あるいは、1 人が 1 問を実装して、残り 2 人が別の問題の解法を考える戦略である。
    • 3 対 2 戦略 B は、2 人が 2 問に取り掛かり、残った 1 人が他の 2 人のヘルプに回るという戦略である。
    • 3 対 1 戦略は、3 人で協力して 1 問を考えるという戦略である。ほぼ適用されない。

2024 年 3 月中旬 (30 日前)

前述の戦略を踏まえてチーム練習を行った結果、かなり良い成績を残すことができました。この段階でようやく、もしかしたらメダルが狙えるのではないかというレベルに達しました。

2024 年 3 月下旬 (20 日前)

この時期は別のイベントとして日本情報オリンピックの春季トレーニングが開催されており、チームメンバー 3 人全員がチューターを務めていたため、チーム練習は行いませんでした。

また、イベント後もチームメンバーの 1 人が新型コロナウイルスの濃厚接触者になったりしたため、チームで集まった練習ができない期間が 2 週間ほど続きました。

本番 10 日前

4 月に入り、いよいよ本番が間近になったため、ICPC 世界大会の過去問を解き始めることになりました。4/3 には 2018 年の過去問、4/5 には 2017 年の過去問を解きました。いずれもメダルを取れそうな結果に終わりました。しかし、コンテスト中の緊張など、これまでの練習では無かった課題も明らかになり、様々な対策を考えました。

本番 7 日前

1 週間前からはタイピング練習を行いました。競技本番は普段使っている日本語配列ではなく US 配列を使う必要があるため、それに慣れるための練習を行いました。最初は (, ), [, ] などの特殊な文字の位置に慣れるのに苦戦し、毎分 200 打鍵程度しか出ませんでした。しかし、

  • ダイクストラ法のプログラム (1000 バイト程度) を 50 回書く
  • セグメント木のプログラム (1500 バイト程度) を 10 回書く
  • 典型問題 20 問のプログラム (書くだけで 1.5 時間かかる) の実装を 4 周する

といった鬼のような練習を行った結果、3 日後には毎分 360 打鍵程度と、日本語キーボードの 90% 以上の速度が出るようになりました。

本番 5 日前

同時並行で、コンテスト本番で使うライブラリ資料の作成も行いました。ここでライブラリ資料とは、いわゆるカンニングペーパーのようなもので、典型テクニックを実装したプログラムを書くチームが多いです。

ライブラリ資料を作る上で難しいことは、チームで A4 用紙 25 枚という制限があることです。そのため、どれを書いてどれを書かないかを選ぶ必要があります。私達のチームでは 2 時間ほどのミーティングを行ってどれを書くかを決め、その後各自で準備を行いました。

本番 3 日前

4 月 10 日、世界大会前最後の大学の授業がありました。12 時に授業が終わり、その後他の同級生に ICPC について話した後、「これが日本の底力なんだ」ということを世界に見せるぞと誓って 13 時に帰りました。

本番前々日

最後の個人練習を行いました。

本番前日

最後のチーム練習を行い、2019 年大会の過去問を解きました。そして 17 時にチーム練習が終わり、いよいよ本番を残すのみとなりました。


4: ICPC 2023 参加記：コンテスト本番

それでは最後に、4/14～19 に開催された ICPC 2023 エジプト大会の参加記を記したいと思います。

4/13～14

世界大会への最初のステップは、エジプトのルクソールまで移動することです。私達のチームは 4/13 15 時頃に成田空港に到着し、17 時半発の飛行機に乗りました。アブダビ、カイロを経由し、トランジット含めて 27 時間のフライトの末、現地時間の 4/14 14 時頃に目的地のルクソールに到着しました。

4/15

この日は午前中に観光があり、午後に開会式がありました。

観光では Karnak Temple に行きました。エジプトだから当然ですが、一面茶色ばかりでびっくりしました。なお、Karnak Temple だけでなく、エジプトの他の建物も茶色系の建物しかほぼありません。

続いて、開会式ではルクソール知事を含む偉い人が次々と出てスピーチが行われたり、ICPC に参加するチームが読み上げられたりしました。

4/16

この日は ICPC Challenge という、競技本番とは別のコンテストがありました。ICPC Challenge は、1 問の数理最適化の問題が出題されるので、3 時間で出来るだけ良いスコアを出してくださいという形式のコンテストです。上位 24 チームにはスポンサー企業の Huawei からの賞品が授与され、特に上位 8 チームに入ると金賞のパソコンがもらえます。

さて、コンテストはどんな感じだったのでしょうか。私達のチームは、最初の 30 分は最上位を走っていました。しかし、その後上手くいく改善が思いつかず、あまりスコアが伸びずに 2 時間時点で賞品圏内から脱落しました。

そこで 2 時間半が経過した辺りで、あることに気付きます。ICPC Challenge では数十個の入力データのの合計点で順位が決まるのですが、過去の大会では「1 個だけ特殊なデータが入っていて、このケースに対して場合分けをすることで順位が一気に伸びる」ということが何回かありました。今回ももしかしたらそれかもしれない、と思いケースを分析してみたところ、まさに 1 個スコアが伸ばせるケースが見つかりました。

残り 10 分、急いで場合分けのプログラムを書きます。残り 5 分、プログラムのバグを探します。そして残り 3 分、提出すると順位が 30 位から 5 位に上がり、金賞圏内に入りました！

このようにして、私達のチームは Huawei Matebook というパソコンをもらうことができました。しかしもう 1 つ気付いたことがありました。今回は残り 10 分で改善が思いついて金賞圏内に入ったが、もし 10 分遅ければ銅賞にすら入っていなかった。つまりコンテストは運にかなり依存するということに気付かされたのです。そこで ICPC 本番では、「日本代表としての責任とかプレッシャーとかをあまり考えず、最後は運で決まると考えることにしよう」と思いました。

4/17

コンテスト前日であるこの日は、実機演習がありました。実機演習は、コンテスト本番のジャッジシステムや、提出の方法などに慣れるためのコンテストです。私達のチームでは、最初誰がパソコンにログインするか、パソコンの位置をどこにするかなどの細かいことを相談し、本番前の最後の確認を行いました。

4/18

いよいよコンテスト当日がやってきました。以下、時系列で参加記を書いていきます。

[8:00]

チームメンバーの全員が起床し、朝食を食べました。

[10:30]

コンテスト控室に入場し、このタイミングでスマホや時計が回収されました。控室の前には開始までの残り時間が表示された画面が映っており、いよいよ始まるのだと感じました。

[11:20]

競技開始 30 分前、最初のチームがコンテスト会場への移動を始めました。私達のチームは、アジア地区予選は感染症等でギリギリの状態での出場となり、世界大会も一時は延期された。このような経験があったので、最後の最後まで自分が世界大会の競技に出場できるということを信じられませんでした。しかしこの段階で「本当に始まるんだ」と確信し、涙が出ました。10 分ほど涙が止まりませんでした。

[11:30]

その後私達のチームもコンテスト会場に入場しました。そして覚悟を決めました。全力を尽くす。悔いのない試合にする。そして最後まであきらめない。

4/18 コンテスト

[11:50 / 0:00 経過]

そしていよいよコンテストが始まりました。問題は A 問題から K 問題までの 11 問。戦略通り、最初は自分が 2 問、QCFium が 3 問、square1001 が 6 問を担当し、square1001 が「他の人が得意」と判断した 2 問を該当者に渡しました。

その後、square1001 が簡単枠の I 問題の解法を思いついたため、実装を開始し、開始 19 分で正解しました。今度は自分が簡単枠の A 問題を実装し、開始 26 分で正解しました。その後、QCFium が G 問題の解法を思いついたため実装し、開始 56 分で正解しました。この時点では 4 位で順調な展開でした。

[13:00 / 1:10 経過]

しかし、今度は square1001 が D 問題、QCFium が H 問題を実装したものの、両方原因不明のバグに見舞われました (両方バグらせる人が非常に多い問題)。しかも順位表によると、現時点でこれまで解いた 3 問と実装中の 2 問以外は 1 人も解かれていません。そこで私は他の人の手助けをしながら、解かれてない中でも簡単だと思った C 問題と K 問題の解法を考えました。

[14:10 / 2:30 経過]

途中メダル圏外の 26 位まで落ちましたが、2 時間が経過した時点で両方のバグがほぼ解決し、2 時間 20 分までに簡単な 5 問をすべて正解することが出来ました。その間に自分は K 問題の合っている確率 80% くらいの解法と、C 問題の途中のアイデアを思いつくことができていました。

この時点で、順位表では C, F, K の 3 問が解かれており、自分のチームもこの 3 問を解けばメダルは取れるだろうと判断し、各メンバーの得意不得意を考慮して以下の戦略を取ることに決めました。

  • E869120 が C 問題の途中のアイデアを QCFium に教えた後、K 問題を実装する。
  • QCFium が C 問題の考察を行い、
  • square1001 が F 問題の考察と実装を行う。

しかし、現在 14 位でまだメダル圏外、しかも実装できる状態の人は僕しかいない。自分が流れを変えるしかないという状況でした。練習の成果をここで出すしかないと思い、実装を始めました。

[14:40 / 2:50 経過]

20 分の実装とデバッグの末、入力データのサンプルで答えが合いました。この時点で解法が正しいことを確信しました。しかし、まだ微妙な高速化が必要です。既に QCFium が C 問題の解法を分かっていたため、実装権を QCFium に渡し、高速化のアイデアを考えました。

[14:47 / 2:57 経過]

数分考えると、高速化の方法が見えたので必死に実装をしました。そして 3 時間 2 分、ついに提出をし、Accepted (正解) と表示されました。順位が 20 位から 7 位に上がり、流れが変わりました。

[16:10 / 4:20 経過]

その後、square1001 が K 問題を実装しました。この問題は 350 行弱の実装を必要とし、バグらせる人も非常に多い問題です。提出数を見れば、正解 1 に対して不正解 9 と、かなり不正解が多い問題でした。しかし、彼はこれを 40 分で実装・デバッグを終わらせるという超人的な技を成し遂げ、3 時間 53 分で正解しました。その後、QCFium も C 問題を正解し、4 時間 20 分で 8 問正解となりました。この時点で勝率 80% の優勢の状況になりました。

[16:20 / 4:30 経過]

しかし、どうにかメダルを確実にしたいと思い、あと 1 問解くことを目指しました。3 章で述べた「3 対 1 戦略」を適用し、残り 3 問の中で最も簡単な B 問題を取り掛かりました。3 対 1 戦略は、練習でも適用率 10% 程度と珍しい戦略であるものの、最も熱いと言われていた戦略です。

この問題は、入力が実質的には N ひとつしかなく、スコアが最大になるような出力をしてください、という形式の問題です。3 人全員で協力して考えます。すると終了 25 分前に square1001 がそれっぽい解法を思いつきます。その後、最初に解法を思いついた square1001 が実装を始め、他の 2 人はより高いスコアを出せないかを考察します。

[16:40 / 4:50 経過]

実装を終え、提出すると不正解が出ます。つまり、より高いスコアが出せるということです。5 分前、3 人全員で必死に考察を進め、N = 6 でスコアを上げる方法が分かりました。不正解。2 分前、N = 10 でスコアを上げる方法が分かりました。それでも不正解。最後まであきらめずに考えましたが、ここでコンテストが終わり、8 問正解で終わりました。

さて、コンテスト終了後も開始 4 時間時点での順位表しか見られないため、自分たちのチームはメダルを獲得したか分からない状況でした。15 位以内に入っている自信はあったものの、12 位に入っている確率は 80% 程度、と思っていました。

そうこうしているうちに、20 時に結果発表が始まりました。成績の低いチームから順位が発表されていきます。60 位、50 位、40 位、30 位と発表されていき、緊張の時間が続きます。しかし 22 時頃、ようやく画面に「Medalists - The University of Tokyo」と表示され、自分がメダルを獲得したことが明らかになりました。この時は本当に嬉しく、国内予選から 2 年間このチームでやってきて良かったと思いました。

そして 4 月 20 日に帰国し、日本に銅メダルを持って帰ることが出来ました。めでたしめでたし。


5. おわりに

ICPC 2023 世界大会への参加にあたっては、たくさんの方の応援がありました。まずは応援してくださった方々に感謝申し上げます。また、一次予選・二次予選・運営に携わってくださった皆さんに感謝申し上げます。これが無ければ私達のチームが世界大会に出場することはなく、メダルを取ることもありませんでした。

最後に、チーム Time Manipulators のメンバーに感謝申し上げます。本当にありがとうございました。



  1. ICPC 2016 プレゼント交換会 の設定を少し変えたバージョン。↩
  2. かなり複雑なので詳細は略します。↩
  3. ここで、目標がメダルだけではない理由は、コンテスト本番のメンタルや心構えに影響するからです。↩