1. はじめに
こんにちは、お久しぶりです。東京大学 修士 1 年の米田 (E869120) と申します。
私達は、今年 8/31～9/5 にアゼルバイジャン のバクーで実施された大学対抗プログラミングコンテスト (ICPC ) の世界大会に東京大学 のチームで参加し、日本国内史上最高成績となる世界 2 位を獲得しました。本稿では、その報告について記します。*1
なお、本稿は ICPC や競技プログラミング を知らない、一般読者でも読めるように書いてあります。皆さんぜひお読みください。
ICPC の表彰式での写真
まず、ICPC の概要について、手短に説明します。
ICPC は大学生・大学院生を対象とした、プログラミングの大会 です。
ここで、プログラミングの大会と聞いたら、皆さんの多くは「ゲームやアプリなどを開発する大会」を思い浮かべる方が多いのではないかと思います。しかし、ICPC はそれとは一線を画し、プログラミングの難問を解く大会となっております。
もう少し詳しく説明すると、ICPC は有名な「数学オリンピック 」とよく似ています。数学オリンピック は、全世界から天才が集まり、4 時間・5 時間といった長い時間をかけて数学の超難問を解き、正解数を競う大会です。一方、ICPC は、数学オリンピック のプログラミング版、といっても間違いではありません。正しくプログラムを書くのが難しいだけでなく、正しい解法を思いつくことすら難しい問題 が多く出題され、プログラミング能力と思考力の両方が試される大会となっています。
ICPC 世界大会の様子
2.1. ICPC のルール
それでは、ICPC の具体的なルールを説明します。
ICPC は 3 人 1 組のチーム戦であり、同じ大学から 3 人のチームを組んで戦います。また、世界大会では制限時間 5 時間の中で 12 問の問題を解き、正解数を競います。
ただし、正解数が同じ場合はタイムペナルティで順位付けされます。タイムペナルティは所要時間の合計であり、たとえば 1 問目を開始 10 分後、2 問目を開始 60 分後に解いた場合、ペナルティは 10 + 60 = 70 分となります。
また、プログラムの提出は競技時間中いつでも行うことができ、数分以内に自動で採点されます。参加者が採点結果を見ることもでき、何回でも再提出することができます。しかし、誤答を出すとタイムペナルティがその分増えるルール (1 回につき 20 分のことが多い) になっているため、速さだけでなく正確性も必須です。
ここで、ICPC には特別なルールがあります。チームは 3 人なのに、パソコンは 1 台しかありません。つまり、同時にプログラムを書けるのは 3 人中 1 人だけです。したがって、他の 2 人をどう使うかなど、戦略やチームワークも重要になります。
順位表のイメージ。緑色が正解を意味する。
2.2. ICPC の選抜
次に、ICPC のスケジュールおよび選抜方法について紹介します。まず、ICPC は毎年開催され、以下の 4 つの段階からなります。
毎年 7 月: 国内予選
毎年 11-12 月: アジア大会 予選
翌年 2-3 月: アジア大会 決勝
翌年夏ごろ: 世界大会
国内予選には日本から約 400 チームが参加しますが、アジア大会 予選に出場できるのは約 50 チーム、アジア大会 決勝に出場できるのは約 10-15 チームと絞られていきます。
そして、今年世界大会に出場したのは、東京大学 (チーム Screenwalkers)、京都大学 (チーム Objective-KUB1)、東京科学大学 (チーム Bocchi The Tech)、徳山高専 (チーム XNOR) の 4 チームのみです。世界大会に出場するだけでも、倍率が 100 倍に達する厳しい選抜となっています。
ICPC の選抜の流れ
しかし、それで終わりではありません。当然ですが、世界大会の中でも順位が付きます。世界大会の参加チーム数は約 140 ですが、その中でメダルが授与されるのは上位 12 チームのみです。具体的には、9-12 位が銅メダル・5-8 位が銀メダル・1-4 位が金メダルとなります。ここで、ICPC の予選に参加するチームは全世界で 10,000 チーム以上あるので、金メダルを取れる割合は 2,500 分の 1 以下となります。
このように、ICPC 世界大会で金メダルを取るのは極めて難しい挑戦となります。
ここで、日本は ICPC において強豪国であり、近年は (新型コロナの影響で東大が出場しなかった 2020 年大会を除き) 7 年連続でメダルを獲得しています。金メダル獲得もあります。しかし、過去最高順位は 3 位であり、優勝などの経験はありません。
過去の ICPC における日本トップチームの順位
2.3. ICPC の重要性
次に、ICPC がどのような意味で重要な大会であるかを記します。
プログラミング能力を競う大会 (競技プログラミング といわれている) には様々なものがありますが、その中で最も大規模で、予算やスポンサーも大きい大会は以下の 2 つといわれています。
特に、今年の IOI や ICPC は OpenAI などの有名企業もスポンサーとして参加しており、つい先週、OpenAI のモデルが ICPC で全問正解したことが話題になりました。
このように、ICPC はただの「プログラミングの大会」の域にとどまらず、多くの大学生や企業が注目する、非常に重要なコンテストとなっております。
3. ICPC 2025 世界大会までの道筋
それでは、いよいよ本編として、参加報告に入りたいと思います。まずは ICPC 2025 世界大会に私達のチームが参加するまでの道筋について記します。私達はどうやって勝ったのか、どのような戦略を立てたのか、そして何を大切にしたのかなどか書かれていますので、是非お読みください。
3.1. チームについて
私達は、以下のチームメンバー 3 名からなるチーム「Screenwalkers」を 2024 年 5 月に結成し、今シーズンの ICPC に参加しました。
米田優峻 (E869120 / 東京大学 修士 1 年)
米田寛峻 (square1001 / 東京大学 修士 1 年)
児玉大樹 (Kodaman / 東京大学 学部 2 年)
3 人全員について、中学生から競技プログラミング を始め、国際情報オリンピック (IOI) の参加経験があるメンバーとなっております。しかし、個人の実力では、日本国内でもより強い選手がおり (実際、個人力*2 では京都大学 のチームよりも弱い！)、最終的にはチームワークを重視したチームとなりました。
チーム Screenwalkers のメンバー (コーチを含む)
3.2. 国内予選
まず、最初の関門は国内予選 (2024 年 7 月) なのですが、結論から書きますと、チーム Screenwalkers の出発は「最悪」でした。
私達のチームは、一応国際情報オリンピック (IOI) のメダリストが 3 人揃っているため、上位を獲得すること、あるいは優勝することが期待されていたチームでした。しかし、結果は 11 位 となり、期待を大きく裏切る結果となりました。
上に東大のチームが 1 チームしかいなかったため、偶然通過しましたが (ICPC では同校制限というものがある)、東大から予選に出て 11 位を取るというのは本来 90% くらいの確率で「予選落ち」となる順位であり、絶望的な状況でした*3 。
国内予選の結果 (Screenwalkers は 11 位)
3.3. 国内予選からの脱却
しかし、それでも予選を通過した以上、現実を見なければなりませんでした。自分のチームに何が足りないのかを真剣に考えました。
考えた結果、まだ国内予選はチーム結成初期であり、チームの戦略などに問題があるのではないかと結論付けました。
そこで戦略を改善するため、Universal Cup という上級者向けのチームコンテストに毎週参加することになりました。また、それ以外にも、アジア大会 予選の過去問を中心としたチーム練習を週 1-2 回行ったほか、個人の実力を上げるために、個人練習も行いました。特に、ICPC 特有の実装力 (プログラムを正確に書く力) の向上を狙いました。
その結果、練習での順位が少しずつ良くなっていきました。Universal Cup では、最初に参加した 2024 年 9 月は 30 位前後 (国内予選に換算して 3 位相当) の成績でしたが、同年 11 月には 15 位前後 (同 1 位相当) の成績が取れるようになりました。
そして 2024 年 11-12 月にかけて、アジア地区予選の台湾大会および日本大会に出場し、いずれも優勝 という結果となりました。
なお、台湾大会および日本大会については、詳しくは以下のブログに書かれています (競技プログラミング 参加者向けの記事となっています)。
日本大会での優勝
ここで、後付けになりますが、これら 2 大会の優勝は今後のチーム Screenwalkers にとって大きな自信になりました。
つい 5 カ月前は国内予選で 11 位を取り、正直、ICPC だけでなく、人生すべての自信を失いました。しかしその状態から、2 連勝を成し遂げることが出来ました。
こんなチームは後にも先にもいないと思います。でも、Screenwalkers で一致団結すれば、不可能を可能に変えられる、Screenwalkers には絶対何かがある、そう思ったのです。
そして流れに乗ったまま、今年 3 月上旬に開催されたアジア大会 決勝を迎えました。途中トラブルがあったものの、終了 10 分前に難問を正解し、ギリギリでの優勝となりました。そしてアジア太平洋地域トップの成績で、晴れて世界大会出場となりました。
アジア大会 決勝での優勝
3.5. 転換点 (1)
さて、世界大会出場が決まったわけですが、そこで現実を見るか見ないかでは大きな差が出ます。
私達のチームは、トップの成績で世界大会出場となりましたが、実はまだ
世界大会で金メダルはまず取れない
世界大会でメダルを取れる確率も 50% 程度
という実力でした。なぜなら、例年ロシア・中国・アメリ カなどから強豪チームが出場する一方、今年のアジア太平洋地域には、圧倒的に強いチームがいなかったからです。
なお、中国は一般的にアジアに属しますが、ICPC では「アジア太平洋地域」ではなく「東アジア地域」という独立した地域になっているため、3 月に実施されたアジア大会 決勝には参加していません。
3.6. 転換点 (2)
そこで、私達のチームと、世界大会で安定して金メダルを取れるチームの差は何なのか、ということについて再考しました。
まず、最も重要な差は個人の実力 にありました。競技プログラミング で最も有名なオンラインコンテストとして、CodeForces というものがあるのですが、私達のチームメンバーは全員、概ね世界 100-200 位の範囲に属していました。しかし、世界大会でメダルを取る大半のチームには、少なくとも 1 人、世界のトップ 50 程度しか取れない「Legendary Grandmaster」の称号を持っている選手がいました。つまり、エース不在 であることが、私達のチームの問題点でした。もちろん、国内予選からの実力の向上はあるものの、Legendary Grandmaster には全く届かない状況でした。
しかし、これはただの言い訳にすぎません！CodeForces と ICPC では競技の性質が全く違う上、さらに過去の世界大会では、エース不在でも金メダルを獲得したチームもいくつかありました。
昨年の世界大会の順位表 (先頭黒+赤の名前が Legendary Grandmaster)
特に、私達のチームは全員が「ある程度強い」ので、それを活かした「バランス型のチームとしての戦略」が絶対にあるはずです。
そこで私達は、チーム戦略をさらに洗練させることに決めました。
まず、ICPC では本質的に何が重要であるかを考えました。考えに考えた結果、難しい問題をじっくり考える力よりも、問題をとにかく早く解く力 の方が重要であることが判明しました。なぜなら、メダルギリギリの世界 10 位くらいのチームが、1.3 倍でも速く解けるようになれば、多くのケースで金メダルを取れてしまうからです。
そこで、速さを上げるため、バランス型のチームにしか出来ない 3 つの変更を行いました。*4
変更点1: 序盤からチームプレイを行う
1 つ目は、序盤からチームで協力して問題を解くということです。これまでは、2 人以上で協力して解くのは中盤以降だけでしたが、練習を行うと
いくら簡単な問題でも、一定の確率で自力で解けないことがある
ということが判明しました。さらに、一定の確率がかなり高い (1 回のコンテストで 1-2 回は起こる) ことが判明しました。
そこで私達は、序盤から解法を共有したり、一定時間手が止まったら他の人に問題を渡したり、場合によっては一緒に考えたりする戦略を採用しました。
(ここで、簡単な問題から他の人に渡したりするのは、かなり心理的 ハードルが高いのではないかと思う人もいますが、実際はかなり有効です。詳しくは 4 章に書きますが、実際の ICPC 世界大会では序盤から多くの問題でチームプレイが起こっています。)
変更点2: ローテーションを行う
しかし、問題の共有が何回も起こった場合、そのぶん時間を使ってしまうため、不利になります。そこで私達は、独自のローテーション戦略 を採用しました。
ローテーション戦略とは、下図のように、ある時間で区切って解く問題を変えるという戦略です。そうすると、同時に 2 人が同じ問題を見る時間がほとんど無くなる一方、1 つの問題を複数人で見れるため、効率的です。
ローテーション戦略のイメージ (ただし、解法が分かった問題が出た場合は、その人がプログラムの実装を始めるため、3 巡目に入ることは多くありません)
変更点3: 実装方針を丁寧に考える
ICPC において、もう 1 つの戦略上の問題は、パソコンが 1 台しか使えないことです。そのため、もし解法が早い段階でわかっても、実装 (プログラムを書くこと) に時間がかかったら意味がありません。そこで私達は、次のような戦略を取ることにしました。
どのような流れで実装するかを、数式を含めて紙に書く。
なお、私達はこのことを「実装方針を詰める」 と呼んでいます。
もちろん、実装方針を詰める作業には数分の時間がかかります。しかし、それにもかかわらず、本戦略にメリットがあると私達は考えました。なぜなら、時間を取るタイプのミス (プログラムのバグ) の多くは
プログラムの書き方の流れを間違える
数式を間違える
などの根本的な部分で起こるからです。逆に、プログラムの変数名を間違えるだとか、for 文の i と j を間違えるだとか、そういった細かいミスはあまり時間が取られません。
3.7. 世界大会に向けた練習
以上の 3 つの戦略を採用し (もちろん他にも様々な戦略がありますが、本稿では省略します。)、5 月以降は週 2-3 回のペースで練習を行いました。その結果、7 月上旬までの練習*5 について、15 回中 13 回でメダル相当の結果を取ることが出来ました。
特に伸びたのは序盤戦でした。これまでは、私達のチームはむしろ序盤に弱く、12 月の日本大会のように終盤で逆転する傾向がありました。しかしチームプレイの結果、最初の 1-2 時間での順位が金メダル圏内に届くことも多くなりました。
そして 7 月中旬の時点で、メダルを取れる確率が 80% 前後に達したと判断したため、チームで話し合い、目標を銀メダルおよび金メダルに上げる ことを決めました。
また、7 月以降の対面での練習では、本番での緊張感を再現するため*6 、本番の順位表を模した順位表を独自に作成し (実装に 500 行くらいかかった…)、モニターに投影しました。
本番モニターに表示される画面の例。タイマーや順位表だけでなく、正解数なども画面が切り替わって表示される。
3.8. 本番 1 カ月前 (8/1～8/10)
いよいよ本番 1 カ月前の直前期になりました。
まず、私は 8/5-9 に開催された、清華大学 主催の練習会に参加しました。この練習会は、例年中国の代表選手 (北京大学 ・清華大学 ・上海交通大学 など) が多数参加するのですが、今回は私達も一緒に、実際に中国の北京まで行って参加しました。
ここでも戦略を大幅に改善し、特に複数人が同時にミスった場合の戦略を大きく変更しました *7 。これにより、序盤だけでなく中盤にも強くなりました。
練習会の結果は、初日は 11 位 (世界大会 20-30 位相当) だったものの、戦略の改善によって右肩上がりとなり、3 日目では全体 2 位 (同 3 位相当)、4 日目では優勝 (同 2 位相当) という結果になりました。
ここで、練習会が終わった時点で、もしかしたら金メダルや優勝のチャンスもあるのではないか 、と思うようになりました。
中国・北京の街並み
さらに、自分のチームの強みもわかりました 。練習会によって、自分のチームが
中盤以下の問題を早く解くこと
誤答を出さずに正確に解くこと
の両方について、中国相手でも十分戦えるほど得意であるということが発覚したのです。実際、成功した 2 回はすべてタイムペナルティの差で勝利したのです。前述の通り、序盤戦が上手いのは自覚していましたが、誤答数については分析しておらず、さらに、速さがそこまで大きなアドバンテージになることは思っていませんでした。
このように、中国での練習会は非常に実りある 1 週間になりました。
3.9. 本番 3 週間前 (8/11～8/17)
同時期に、世界大会の過去問を解き始めました。
最初の世界大会 (2016 年度) の結果は、今年のレベルに換算して 17 位相当、メダル無しの結果となりました。しかし、ここに来て戦略の大きな穴が発覚したのです！
ICPC 世界大会は、他のコンテストと比べて、問題文を読み間違えやすい という傾向があります。しかし、私達はその対策をほとんど行っていなかったため、最初の過去問演習では、複数の問題で誤読をしてしまい、メダル無しという結果になってしまいました。
そこで以下のような戦略を立てました。
問題文を読んだ後、問題文の最後に書いてある「例」のセクションを読んで検証する。
問題文を共有するときは、誤読しそうな部分も合わせて伝える。
その結果、誤読がやや少なくなり、5 回の世界大会過去問のうち 2 回で金メダル相当*8 を出すことが出来ました。しかし、「コンテストの成績」と「誤読の多さ」には依然として強い相関があり、課題も残りました。
2021 年度の世界大会の結果
3.10. 本番 1 週間前 (8/24～8/27)
締切が迫っているチームのライブラリ (カンペのようなもの) の準備を進めました。ライブラリは 25 ページ制限があるため、枚数を収めるのに苦労しましたが、やはりタイムペナルティ重視のチームであるため、「網羅性」よりも「簡潔かつ間違えにくい実装」 を心掛けました。また、解く時間を 1 パーセントでも削るため、戦略についてもさらに深く考えました。
3.11. 出国当日 (8/28)
いよいよ出国当日となりました。
出国当日は、11 時頃に荷物を持って東大の本郷キャンパス に集まり、昨年度の世界大会の過去問を解きました。ディスプレイ・キーボード・コンテスト環境等含め、すべて本番同様の環境で行いました (セットアップに 1 時間ほどかかりましたが)。*9
17 時頃に最後の練習が終わり、羽田空港 に向かった後、コーチと合流して 19 時から壮行会を実施しました。国内予選 11 位だったことを思い出し、我々にはチームの力がある、チームで協力したからこそ実力を上げられたのだ、と感じました。最高の結果を目指すと誓って壮行会が終わり、空港のカウンターに向かいました。
そして 22 時 50 分、私達は決戦の地・アゼルバイジャン のバクーに向けて出発しました。
バクーにはカタール を経由して行きました
4. ICPC 2025 世界大会参加報告
それでは、ICPC 2025 世界大会の参加報告に入りたいと思います。
4.1. 出国 (8/28～8/29)
まず、私達は 8/28 の 22:50 に羽田空港 を出発し、カタール のドーハを経由して、8/29 の現地時間 12:35 にアゼルバイジャン のバクーに到着しました。空港からは、運営のバスでホテルに向かいました。
なお、実際に入国が想定される日は 8/31 なのですが、時差やコンディションの調整のため、2 日早く現地入りしました。
バクーの空港には ICPC の掲示 が書かれていた。国家的イベントであることがうかがえる。
4.2. 観光 (8/30)
早めに現地入りしたので、8/30 はバクーを観光しました。有名な旧市街を散策し、その後カーペット美術館にも行きました (アゼルバイジャン ではカーペットが非常に有名らしいです)。
旧市街の様子
4.3. 最終調整 (8/31)
8/31 には既に、京都大学 のチームも現地に到着していたため、合同で最終調整を行いました。その後、参加登録 (書類を書いたり、写真撮影を行ったりする) を行いました。
4.4. 前座 (9/1～9/2)
9/1 からの 3 日間は、いわゆる「前座」的なイベントが開催されました。まず 9/1 には、午前中に有名な論文の著者の講演が行われた後、午後に開会式が実施されました。開会式はアゼルバイジャン で最も有名な建物の 1 つである、ヘイダル・アリエフセンターで実施されました。
ヘイダル・アリエフセンター。かなり特徴的な形をしている。
9/2 には実機演習という、本番のパソコンに慣れるための練習を行いました。自分が想定していたキーボードと、本番用キーボードが微妙に違ってやや焦りましたが、実機演習である程度慣れました。さらに、ロビーにたまたま置いてあった本番用キーボードを使って練習した結果、十分に慣れることができました。
4.5. 前座 (9/3)
次に、9/3 には ICPC Challenge という、中国の大企業 Huawei 主催のコンテストが実施されました。本番のコンテストとは異なり、正解のない最適化問題 で出来るだけ良い解を出す形式のコンテストでした。制限時間は 3 時間で、チーム全員で協力をして問題を解く形式でした。
ここで私達のチームはなんと「優勝」 となり、豪華景品としてパソコンをいただきました。
なお、本編ではないのでコンテストの様子は手短に書きますが、以下のような展開だったと思います。
序盤は点数が伸び悩んだが、コンテストの中盤に重要なアイデア を発見し、一気に順位を上げて 2 時間時点で 1 位。その後も 2 時間 15 分くらいまでは点数を伸ばす。しかし、その後もいろいろな解法を思いつくが、実装しつつ時計を見ると残り 10 分、どのアイデア も時間が足りない。他のチームも点数を上げ、終盤に伸ばさなければ優勝できない状況。チームで一丸となって、残り 10 分で出来ることを考える。 そこで数行の追加とパラメータの変更、そしてわずかな定数倍高速化で点数が有意に伸びる可能性を指摘される。それを 1 つずつ直していくと、少しずつ点数が伸び、残り数分の提出で優勝を決めた。
あまりにもギリギリの勝ち方だったので、もし本番優勝することがあるとしても、まず間違いなくこのような際どい勝ち方になる、ということを再認識しました*10 。そして、どんな場合でも絶対におごってはいけない、ということを改めて感じました。
夜は、少しバクーの夜景を見てからベッドに入りました。月がちょうど 8 割くらい満ちていたので、「明日の世界大会が最後の 1 ピースか…」「絶対に最後の 1 ピースを埋めなければならない」と覚悟を決めました。*11
競技前日のバクーの夜景
4.6. 競技本番 (9/4)
いよいよ競技本番の朝を迎えました。中学 1 年に競技プログラミング を始め、学生競技プログラミング の大会は今日で最後*12 。つまり 10 年間の集大成となります。チームとしても、絶対に負けることはできません。
競技は 11 時頃から始まりますが、8:45 頃のバスに乗り、競技会場には 9:10 に到着。しばらくした後控室への入場が始まったため、チームで円陣を組み、コーチとはここで別れました。
10:20 頃、いよいよコンテスト会場への入場が始まりました。私達は、高校野球 の甲子園などと似たように、東大のロゴが書かれたプラカードを持って入場しました。入場した時、涙が出ました。国内予選で 11 位の絶望から、チームの力で困難を乗り越え、不可能を可能に変え、ついに世界大会のこの場に来れた。そう思っていろいろな感情が出てしまいました。15 分ほど泣きましたが、コンテスト開始前のアナウンスが出た頃には覚悟を決めました。
10:40 頃、すべてのチームが入場し、開始前の説明 (緊急時の対応など、いわゆる離陸前の機内ビデオのようなものです) が流れました。そして 10:45 頃、戦略に関する最後の確認を行い、いよいよコンテストが始まります。
諸注意
以下の項は、諸事情によりすべて「で・ある調」に書き換えて書いています。不自然に感じたら申し訳ございません。なお、コンテスト中の実況は、以下の YouTube にも配信されています。
それでは以下、コンテストの様子について記します。楽しんでお読みください (多少競技プログラマ 向けの説明が入るので、ついていけなければ読み飛ばしても構いません)。
コンテスト開始
開始。まず自分が環境のセットアップを行い、square さんが問題を開く。問題は 12 問で A から L までの番号が付いている。自分が A-D、square さんが E-H、Kodaman さんが I-L を読み、解法を考える。ここで、ICPC 世界大会の問題は難易度順に並んでいるわけではないため、どれが簡単かは時が経つまで分からない。
開始 6 分、L 問題が解かれ、これまで他の 3 問を読んでいた Kodaman さんが L 問題を読む。小考の後、開始 12 分頃に実装を始める。自分が読んでいた D 問題は問題文の読解が難しかったが、練習の通り例まで確認する。順位表を見ると、D 問題も解かれたので解法を考え、比較的簡単に思いつく。ちょうどそのタイミングで Kodaman さんが L 問題を正解する。その時点で 30 位前後。少し出遅れるも、1 問目の出遅れは挽回可能との経験則から落ち着く。*13
続いて自分が D 問題を丁寧に実装し、開始 25 分で正解。そのタイミングで square さんが F 問題の解法を思いつき、実装。開始 34 分で L・D・F の 3 問正解となり、この時点で 3 位。
開始 40 分時点での順位表。緑が正解を表す。+ に付いている数は誤答数。
ここで square さんの実装中に、Kodaman さんが J 問題の解法の前半部分を思いついたので、自分に共有。その後、競合を起こさない「ローテーション戦略」で Kodaman さんに I 問題の解法を考えてもらう。しばらくすると解法が思いついたと言うので 3 問正解の後に実装。
しかし、I 問題の解法が間違っていることが発覚。さらに J 問題も場合分けをミスりやすい問題で、自分が 1 回誤答を出してしまった。
2 問同時デバッグ という危機的状況の中、打開策として square さんが I 問題のヘルプに回ると、解法の修正に成功。実装は元通り Kodaman さんに任せたため、展開としては、自分と Kodaman さんで I と J の 2 問を並列に実装し、実装していない時間は他の問題を考えるということになった。
2 問を追う状況で一瞬 19 位まで落ちたが、開始 1 時間 6 分で I 問題、開始 1 時間 12 分で J 問題を連続で正解。この時点で 2 位。さらに、square さんが既に H 問題の解法を思いついており、自分と考察を共有して正しいという結論になったため、すぐに H 問題の実装を始められる状況となった。これで状況は打開された。
開始 1 時間半時点での順位表。
ここから中盤戦に入る。この時点で既に 9 問が解かれていたため、今回は簡単寄りなセットであり、メダルには少なくとも 9 問が必要であると確信する。
その後、square さんが H 問題を実装し、自分と Kodaman さんは K 問題を共同で考察する。方針がある程度わかった段階で残りのすべての部分を Kodaman さんに投げ、自分は A 問題などの他の問題を考える。開始 1 時間 35 分で H 問題、開始 2 時間 6 分で K 問題を正解。この時点で 7 問正解となり、ペナルティの合計が 455 分で暫定 1 位。
しかし、数分後には後追いの 7 問正解が次々と出現し、1 位は守っているものの 2 位と 5 分差とかになった。さらに 8 問正解が誰もいないのに 7 問正解が 10 チームくらいあるような状況になり、「なんでこんな僅差なんだ」とつい言ってしまった気がする。競技プログラミング というより、駅伝のような試合展開である。
ようやく 8 問正解が出た時点での順位表。その前は 7 問正解で並んでいた。
この時点で、自分がようやく A 問題の最初のアイデア を思いつき、Kodaman さんに共有する。実装できる部分を実装しながら、10 分ほど次のアイデア を相談すると、解法が思いつく。細かい部分を整理するパートが大変だが、ここで時間を使うとペナルティの有利が無駄になってしまうため、できるだけ早く 8 問目を解く必要がある。整理パートの分担が可能な問題だったので、分担して考察をすると、ついに開始 2 時間半前に実装が出来る状態になる。
実装中、square さんがまだ 3 チームしか解いていない E 問題 (A 問題より難しい) の解法を思いついたと言う。誤答が多い問題なので、Kodaman さんに解法を細かく検証してもらうと、なんと合っているという結論になる。ここまで一番のファインプレーである。
現時点で実装できる問題が 2 問あるので、手が止まったらパソコンを代わる「並列実装」を行う。まず、今実装中の A 問題の入力例が合わないので、E 問題と交代し、自分は紙の上でのデバッグ を行う。その後 E 問題も合わないので今度は自分がパソコンを使う。
3 回くらい交代した気がするが、気づいたら square さんが E 問題を提出し、一発で正解していた！ここまでペナルティ 639 分で 8 問正解。後は自分が A 問題さえ通せば、当初の目標のメダルは盤石、速度によっては金メダルも狙える。しかし通せなかったら負け。ここが正念場である。
開始 3 時間 15 分、適宜 Kodaman さんと協力しつつデバッグ を行い、入力例が概ね合ったため順位表を見る。現在の順位表は以下の通りであった。
開始 3 時間 15 分前後での順位表。
9 問正解が 3 チームいるが、865 分・865 分・887 分の接戦である。それに対して自分は 8 問正解で 639 分。つまり、開始 3 時間 45 分までに A 問題を一発で通せば 9 問の中で 1 位となる。しかし、1 回でも誤答を出せば 20 分が加算されるため、集団の中で 3 位、あるいは 4 位にすらなれない可能性がある。
10 問目の B 問題が難しいことが徐々に判明しつつあるため、最終的に B 問題が解けず、9 問勝負になる可能性もある。この場合、A 問題で全部決まる。さらに、もし B 問題が解けて 10 問勝負になったとしても、ペナルティの計算式上、残り 1 問でペナルティの差を逆転するのは難しい。とにかく、勝つためにはペナルティを 865 分未満、10 問勝負を考慮すると出来れば 840 分台にする必要があり、ミスは絶対に許されないのである。
そのような厳しい状況であったため、まず手で十数ケース試してデバッグ を行う*14 。それはとりあえず通る。次に、プログラムのある特定の部分にミスが多そうだという直感があったため、その部分だけを抜き出し、いくつかの例を試す。すると、バグがまだ残っているのではないか！バグを修正し、追加でいくつかのケースを試す。
開始 3 時間 26 分、もうバグはないだろうと思ったタイミングで最後の確認を行い、提出する。誤答ならば大幅に勝率が下がるので恐る恐る順位表を見る。すると 1 分後、正解を表す緑の背景が表示された。ペナルティは 639 + 206 = 845 分となり、9 問時点で 1 位。嬉しくて飛び上がりそうになった。
東京大学 が 9 問正解した直後の順位表。
いよいよ終盤戦である。
開始 3 時間半。順位表を見ると、難しい B 問題を解いている St. Petersburg 大学が A 問題で誤答を出しており、つまり仮に正解したとしても 20 分のペナルティが加算されるため、B 問題を早く解けば 10 問の中でも 1 位になる可能性がある。そうすると金メダルはかたい。一方、残る C 問題と G 問題は誰も解いていない。その時点で、3 人すべての戦力を B 問題 1 問に集中させる、いわゆる「3 対 1」の戦略を取ることになった。
B 問題は実質的に、入力が整数 N ひとつだけの問題である。その時点で、N が小さい場合は解けていたので、N が大きい場合の高速化を考える。しかし、3 人で高速化のアイデア を出し合うも、すべて失敗。プログラムの実行が 1 秒で終わらなければならないという実行時間制限が、厳しすぎるのである。
そこで、N が大きい場合は数学的に解けるのではないかと square さんが言った。「素数 を使えば解けるのではないか」と言ったので、N が小さい場合のプログラムを使って実験を行う*15 。しかし何パターンか実験するも、性質がつかめない。
ここで本問題では、複数の答えが正解になることがあるため、あり得る最小の答えを出力してみる。実験結果を N=300 くらいまで眺めると、square さんの素数 のアイデア と組み合わさり、もしかしてそれなのかもしれない、とひらめいた。
開始 4 時間時点での順位表。まだ 1 位である。
この時点で終了 40 分前。ICPC 世界大会では、最後の 1 時間の提出結果が見られないシステム (順位表凍結とも呼ばれる) になっているため、結果はわからないが、少なくとも開始 4 時間 15 分で St. Petersburg 大学が A 問題に提出している。おそらく、この A 問題は正解であろう。そしてペナルティを計算すると 1140 分であるため、そのチームに勝つには、30 分以内に B 問題を解くのが必須条件である。もちろん誤答は一度たりも許されない。下のチームも考えると、出来れば 20 分以内では解かなければならない。
アイデア が思いついた途端、square さんは必死に実装を始める。自分は実装方針の部分と解法の検証を行い、Kodaman さんはデバッグ 用に N が小さい時の答えを手で計算する。結局 N=20 くらいまで計算してくれたらしく大変助かる。実験プログラムを再利用してプログラムを書き、終了 35 分前、実装が終わるが入力例が合わない。
実質的なタイムリ ミットまであと 15 分。時間が切迫する中、協力してミスを探し、数分後ついに入力例の答えが合う。そして N が小さい時の答えを手計算と突き合せた結果、すべて正解。終了 30 分前、もうこれ以上バグはないだろうと考え、提出をする。緑の四角が表示され、正解。これで 10 問時点での 1 位は確実になった。
終了 20 分前の順位表。黄色はラスト 1 時間の提出 (結果は自分のチーム以外見れない)。
これで 4 位以内の金メダルはほぼ確実になったが、優勝には 11 問が必要かもしれない。残り少ない時間、まだほとんど考えていない C 問題と G 問題の解法を全力で繰り出そうとする。しかし、G 問題の解法は大まかには分かったが、正解するには長いプログラムを書く必要があり、明らかに実装が間に合わない。
C 問題についても考え、勾配降下法で解けるのではないかという気持ちになる。しかしこの問題も思ったより実装が難しく、かつ今考えている実装では実行時間制限に間に合わないケースがあるのではないかという話になる。
残り 10 分頃だったであろうか。ついに打つ手がなくなり、天を仰いだ。これで私の ICPC は終わるのか。順位表を見る。まだ 11 問目の提出はない。金メダルは盤石、もしかしたら優勝もあり得るかもしれない。10 年間の集大成をこのような結果で終われて本当に幸せだ。
そして、チームメンバーの 1 人でも欠けていたら、10 問正解は絶対にあり得なかった。「1 年と少しの間、本当にありがとうございました」。チームメイトに感謝しつつ、コンテストが終了した。
コンテスト終了後の会場の様子 (YouTube より引用)。ICPC では問題を解くと風船が渡されるため、たくさんの風船がある。
4.7. 最終結 果
コンテスト終了後、閉会式および結果発表が行われました。11 問正解の可能性があるチームは、終了 10 分前時点でゼロでしたが、最終的にはロシアの St. Petersburg 大学と中国の北京交通大学の 2 つとなりました。10 問時点では 1 位が確定しているため、最終順位は 1 位・2 位・3 位のいずれかという状況でした。
結果的に、北京交通大学は解けませんでしたが、St. Petersburg 大学は難問の G 問題を 2 度の誤答の末、終了 1 分前に通す大逆転劇を演じ、自分のチームは 2 位となりました。2 位は、日本の二十数年にわたる ICPC の歴史の中で、歴代最高順位を塗り替える結果となりました。
優勝は結果的に僅差で逃しましたが、11 問解かれたのであれば仕方ないと思います。私達のチームは、どちらかといえばタイムペナルティの有利を活かす戦略のチームなので、もし優勝する可能性があるとしても、「同点の中でタイム差で勝つ」シナリオしかほとんど考えられないと思っていました。優勝された皆さんは本当におめでとうございます。
最終的な順位表
5. おわりに
皆さん、本記事をお読みいただき、誠にありがとうございました。競技プログラミング 参加者の方には少しでも参考になっていただけたら、そして一般読者の方には「競技プログラミング って楽しいんだ」と思っていただけたら、本当に嬉しいです。
さて、これで私の ICPC 人生は終了となります。*16
振り返ると、私はこれまでの人生の 4 割超にあたる 10 年間、競技プログラミング に取り組んでまいりました。中学 1 年生の時に競技プログラミング を始め、中高生時代は国際情報オリンピック を目指して練習しました。その後大学に入ると、今度は主に教育に力を入れ、『競技プログラミングの鉄則』 などの本を出版しました。大学 3 年生からは再び選手として活動し始め、今度は ICPC を目指しました。大学 4 年の夏、国内予選で 11 位を取った時は絶望しました。しかし、ついに世界大会 2 位という、望める中で最高の結果で、学生競技プログラマー としての人生を終えることが出来ました。私は本当に幸せ者だと思っております。
そして、今回の結果を残せたのは、たくさんの方々のご支援のおかげだと考えております。皆さん、10 年間本当にありがとうございました。そしてもちろん、私も ICPC で世界 2 位を取った者として、周りにも貢献していくべきだと考えており、少なくとも修士 2 年までは支援活動を続けるつもりであります。出来ることなら何でもやりますという気持ちです。
