ICPC世界大会

初めてのICPC世界大会だったので、ものすごく楽しみにしていた。当時はまだ大会名もACM-ICPC World Finalsだった。

世界大会までの予選については、ここでは省略する。毎年ミシガン州グランドラピッズで戦っていたので、詳しくはいつか予選編にまとめたい。

それにしても、ロシアのビザは本当に大変だった。今まで行った国の中でも、取得が難しい部類に入る。申請には大会側が発行した招待状の原本が必要だった。そもそも大会側に正式な招待状を発行する資格が必要だし、そのうえ原本を国際郵便で送ってもらわなければならない。届いた招待状はいかにも正式なもので、茶色がかった黄色い特殊な紙に、読めない文字、通し番号、僕の名前、署名、印章が並んでいた。それがロシアからアメリカまで海を越えて届く。途中でなくなったらどうするのかと言われても、たぶん諦めるしかない。結局、旅行会社にビザ申請と航空券の手配をまとめて頼んだ。記憶では、ビザだけで一人300ドル以上かかった。大学が負担してくれたのは本当に助かった。

大会前、僕は中国、二人のチームメイトはアメリカにいて、チーム練習はほとんどできなかった。ビデオ通話をつないでオンライン練習を2回ほど試したが、正直ほとんど練習にならなかった。僕が中国へ戻る前も、それぞれ学業が忙しく、三人で練習できたのは数回だけ。あとは各自でやるしかなかった。要するに、ほぼぶっつけ本番だった。

この世界大会への旅は、欠席届を出すところから始まった。大学で正式に休みを取る日が来るとは思っていなかったし、それがこんなに面倒だとも思わなかった。

僕は上海交通大学ミシガン学院の2+2プログラムに所属していた。最初の2年を上海交通大学、その後の2年をミシガン大学で過ごし、最後の学期に上海へ戻って卒業プロジェクトに参加すると、両方の大学の学位を取得できる。上海へ戻らなければ、ミシガン大学の学位だけになる。実際、将来アメリカで働くつもりの学生の多くは、上海へ戻らず、その学期をアメリカでのインターンに使っていた。就職にはそのほうが明らかに役に立つ。そのため、この課程で両方の学位を取る割合はかなり低かった。僕の記憶では――あまり正確ではないかもしれないが――8割未満で、上海交通大学の中でもかなり低いほうだったと思う。

当時の僕は、ちょうど上海交通大学へ戻って最後の卒業プロジェクトに取り組んでいた。必要な単位はすでにそろっていて、その学期は卒業プロジェクトしかなかった。上海へ戻ったのは、将来どこで働くか決めきれていなかったので、とりあえず両方の学位を取っておこうと思ったからだ。とはいえ、実際にはアメリカで働く可能性がかなり高かった。そのため僕自身は妙に気楽で、仮に上海交通大学を卒業できなくても、それほど困らないと思っていた。中国へ戻って友達とひと夏遊んだことにすればいい、くらいの気持ちだった。

背景はここまで。大会の日が近づいてきた。大学生なら授業を休むことくらい珍しくない。これは中国だけの話ではなく、ミシガン大学でも出席を取る教授は少なかった。だからこそ、黙って休むのは普通なのに、正式に欠席を申請すると、とんでもないことをしたような扱いになるのが不思議だった。

もともと欠席届を出すつもりはなかった。その週の授業は2回だけなので、そのまま休めばいいと思っていた。ところが運悪く、卒業プロジェクトの2回目の発表が同じ週にあり、最終成績の5％を占めていた。その5％を失うこと自体は気にしていなかった。単位を落とすことはないと思っていたからだ。ところが、指導教員の取りまとめ役に相談すると、「発表を一度でも欠席したら卒業プロジェクトは不合格だ」と言われた。

さすがに驚いた。5％の発表を休んだだけで、なぜ科目全体が不合格になるのか。シラバスや採点基準など、見つかる資料を全部確認したが、そんな規則はどこにも書かれていなかった。最終発表ならまだ分かるが、これは2回目で、このあとさらに2回ある。なぜそんな判断になるのか、まったく理解できなかった。当時の狭い見方では、僕の申し出が先生の面子をつぶしたと受け取られたのではないか、としか思えなかった。

困り果てて、これは世界大会という重要な大会なので、大学から正式な欠席許可を取れば認めてもらえるかと聞いた。先生は、正式な許可があれば考えると言った。仕方なく、欠席手続きを始めることになった。

まず学生担当の先生に相談した。最終的に何人の署名が必要だったかはもう覚えていない。たしか3人くらいだったと思うが、最初に学生担当の承認が必要だった。大会に出るため休みたいと説明すると、指導教員よりは穏やかだったものの、考え方は似ていた。「なぜ休むのか」「卒業プロジェクトは大事ではないのか」「どうしても行かなければならないのか」と聞かれた。僕の答えは一貫していて、どうしても行く、だった。上に書いた通り、アメリカで働くなら上海交通大学の学位は自分にとってそれほど重要ではなく、なくても構わないと内心では思っていた。もちろん口には出さなかったが、そのせいで態度だけは非常にはっきりしていた。絶対に行く、と。

その強い態度に押されたのかもしれないし、上海交通大学での最初の2年間、学院内GPA2位で学業優秀賞を取っていたため、「真面目な学生」という印象が定着していたからかもしれない。最終的に先生は欠席を認め、「しっかり戦って、大学の名誉のために頑張ってこい」と言った。

ただし、僕が代表していたのはミシガン大学だった。上海交通大学の競技プログラミングチームはもともと非常に強く、僕の助けなど必要ない。そもそも僕が入れるとも思えない。もちろん、その場では何も言わなかった。僕が上海交通大学代表ではないと知ったら、先生はどう思っただろう。

こうして正式な欠席許可と偉い人たちの署名を手に入れ、もう一度指導教員と話した。最終的には、5％を減点するだけで、科目を不合格にはしないことになった。

本当に大変だった。内向的な僕にとって、この一件だけで一年分の社交エネルギーを使い切った気分だった。

これで心配事はなくなった。いよいよ大会へ出発だ。

僕は上海から一人で飛び、チームメイトとコーチはアメリカから向かった。先ほど書いた通り、上海へ戻って卒業する代わりに、アメリカでインターンをする学生も多い。チームメイトの一人もそうだった。彼の夏季インターンは、アメリカのテック企業では標準的な12週間。全部で12週間しかないのに、そのうち丸々1週間を休まなければならなかった。彼にとっても簡単ではなかったはずだ。話を聞く限り、彼も「どうしても休ませてほしい」と押し切ったらしい。リターンオファーを逃すかもしれないリスクを負いながら、何とか1週間の休みを取った。

飛行機はモスクワ乗り継ぎだった。ロシアの別の都市へ行くなら、だいたいモスクワを経由するものらしい。乗り継ぎ自体は順調だったが、入国審査で係官に行き先を聞かれた。僕が「Yekaterinburg」と答えると、相手は「Екатеринбург？」。僕はもう一度「Yekaterinburg」。相手もまた「Екатеринбург？」。しばらくこの繰り返しだった。

誇張ではなく、本当にこんなやり取りだった。僕は英語で話し、相手もほとんど英語だったが、都市名だけはロシア語の発音だった。エカテリンブルクは英語とロシア語で発音、特にアクセントの位置がかなり違う。僕には相手が何を言っているのか、さっぱり分からなかった。

最後には、向こうも僕の行き先を理解したらしく、無事に通してくれた。

エカテリンブルクに到着し、ホテルでチームメイトと合流した。そして三人そろって気づいた。誰も変換プラグを持っていない。

三人とも海外が初めてだったわけではない。もちろんアメリカには行っている。ただ、アメリカでは長く暮らすので、必要なら現地で変換プラグを買う。一方、今回のように本当に変換プラグが必要な国へ短期旅行するのは、三人ともたぶん初めてだった。だから誰一人、持ってくることを思いつかなかった。

代表を一人決め、フロントに借りられないか聞きに行くことになった。その代表が僕だった。当時は英語もあまり得意ではなく、socket、power、chargerなどと順番に言ってみた。するとフロントの人が笑って、「欲しいのはadapterじゃない？」と言った。正直、adapterという単語を知らなかったが、響きからしてたぶんそれだと思った。

こうして変換プラグを一つ借りた。その後の一週間、三人は毎日一つの部屋に集まり、順番に端末を充電した。

大会までの数日間に何をしていたかは、もうほとんど覚えていない。コーチが街の観光地へいくつか連れて行ってくれた気はするが、どこだったかは完全に忘れた。チームにはロシア語を話せる人がいなかった。副コーチは、記憶が正しければ元々ロシア出身だったようだが、何らかの事情でアメリカへ移ったらしい。本人によると、もう一度ロシアへ入ると、今度は出国が難しくなるかもしれないとのことだった。かなり遠回しな言い方で、これはあくまで僕がそう理解したという話だ。彼が一緒なら、もう少し街を見て回れたかもしれない。

そして、ついに大会当日を迎えた。この年の問題セットは、とんでもなく難しかった。ジャッジ、つまり問題を選び準備する人たちが、touristのチームに全完されて時間前に終えられることを恐れ、意図的に難しくしたという噂まで流れた。touristはゲンナジー・コロトケヴィッチのハンドルネームで、当時、世界最強の競技プログラマーとして広く知られていた。前年、彼のチームは全完まであと一歩だった。公式の大会後解説によると、最難関問題には本番直前に3つの極端なテストケースが追加されており、それがなければ前年に全問を解いていたという。

噂の真偽も、なぜここまで難しくなったのかも分からないが、とにかく2014年の問題セットは大事故だった。ずっと後に僕自身が世界大会のジャッジとなり、問題選定の仕組みを知ってからは、なおさらこの年に何が起きたのか分からなくなった。当時の関係者にも何人も聞いたが、返ってきたのは「その年、何か特別なことあったっけ？ 覚えていない」という答えばかりだった。つまり、あの噂はたぶん作り話だ。ジャッジたちにとっては特別でも何でもない普通の世界大会で、単に難易度調整が大きく外れただけなのだろう。

話を大会に戻そう。

Kのファーストソルブは17分だった。15分の時点で、僕たちはすでに何かがおかしいと感じていた。例年なら10分前後で最初の正解が出るはずなのに、この年は15分たってもスコアボードが静かなままだった。Kが解かれたあとも状況は良くならず、むしろ異常さがはっきりした。普通なら、最初に解かれた問題には全チームが集まり、1時間もすれば何十チームも通す。ところが今回は、ほとんど誰も続かなかった。僕たちもKを読んだが、まったく解けず、黙り込んだ。データ構造の問題だとは思ったものの、どう使えばいいのか見えない。適当な最適化を書いて8回不正解を出し、最後まで通せなかった。必要だったのは区間最小値クエリ、RMQだった。当時の僕たちは、こんな基礎的な手法さえ名前を聞いたことがある程度で、誰もきちんと使えなかった。当然、発想にも出てこなかった。

膠着状態が続き、28分にようやくDを解くチームが現れた。僕たちも読み直し、これはいけるかもしれないと思った。最初に読んだときは、簡単な問題には見えず、本当に解けるか確信がなかった。ただ、誰かが通したなら、少なくとも解ける問題ではある。チームメイトの一人がDに取り組み、それから約1時間後、僕たちもACを出した。これがこの大会での最初の正解だった。

35分にはCのファーストソルブが出た。計算幾何の問題で、一見すると解けそうだが、場合分けが多く、通すのが難しいタイプだった。僕たち三人は全員、計算幾何が苦手で、幾何が出るとだいたい僕が勢いで書く担当だった。予想通り、Cは場合分けだらけで、終了までに6回提出したが通らなかった。本番中は正解にかなり近いと思っていた。ところが大会後、自分たちのコードと公式データで試すと、正解からはほど遠かった。計算途中は実数なのに、出力は整数。整数に限りなく近い値が出たとき、状況によって切り上げ、切り捨て、丸めを厳密に使い分ける必要がある。計算幾何初心者の三人に理解できる話ではなく、この問題を通せる可能性はなかった。

68分、Iを解くチームが出た。僕たちも読んだが、やはり解けない。ただ今回は少し違った。ファーストソルブのチームを見て、「え、あのチームがIを通した？ なら何か無理やり通す方法があるはず」と思った。とはいえ、うまいヒューリスティックは思いつかない。結局、最も乱暴な方法、全探索＋時間調整を使った。プログラムは総当たりで探索し、制限時間ぎりぎりになる前に止め、その時点で見つかっている最善解をそのまま出力する。結果として、この方針は正しかった。念のため、固定された入力順を狙い撃ちされないよう、処理前にデータをランダムに並べ替えた。最初の4回は、停止する時間の設定が悪く、早く切り上げすぎるなどして不正解。パラメータを調整した5回目で、ようやくACした。Iを最初に解いたチームは、結局この1問だけで大会を終えた。世界大会史でもかなり珍しい1問だけの成績だと思う。

ほかの正解が出た問題は、僕たちにはほとんど関係なかった。読むたびに、分からない、となって静かに次へ移った。

Bは、多重ナップサックの最適化が必要なナップサックDPだというところまでは分かった。しかし、その最適化を誰も覚えていなかった。実際には、既存の最適化の考え方から、さらに新しい式を導く必要があった。現地でそこまでたどり着く力は、明らかに僕たちにはなかった。

一番悔しかったのはEだ。読んでもまったく方針が見えなかった。実際には、問題全体のロジックがDFA最小化とほぼ同じだった。僕とチームメイトの一人は、そのわずか1年半前に授業で一緒に習っていたのに、二人とも思い出せなかった。本来なら絶好の問題だったのに、本番では結びつかなかった。

Aにも挑戦した。公式参加チームだけでなく、非公式チームを含めても、大会中に解いたチームはゼロだった。僕たちが手を出したのは、ほかにできることがほとんどなかったからでもある。アルゴリズムというより構築とひらめきの問題で、チームメイトは大会中盤から3時間考え続け、2回提出したが通らなかった。大会後、コーチに「あの提出、本気だったの？」と聞かれた。もちろん本気だった。実はAには解法があったのだが、スコアボードに正解が一つもないのを見て、全チームが尻込みしていた。後でジャッジに聞いた人によると、ジャッジ側はAを全問題中もっとも簡単だと考え、ファーストソルブが出たあと大量に解かれると予想していたらしい。これほど大きな認識のずれも珍しい。n mod 4の余りごとに4通りあり、どのケースでも最適解はnになる。チームメイトは3ケースまでnを導けていて、最後の1ケースだけn+1までしか縮められなかった。世界大会でのファーストソルブ、ひょっとすると唯一の正解を取る機会を、あと少しで逃した。本当に惜しかった。

結局、僕たちは2問で大会を終えた。

大会後は、誰もが何とも言えない空気だった。世界大会でここまで難しい問題セットは前例がないように感じられ、touristの全完を防ぐためだったという噂もすぐ広まった。場外のtouristチームは7問を解き、ペナルティも少なく、成績だけなら1位だった。もちろん非公式チームなので順位には入らない。しかも8問以上まであと少しだった。Aには一人が1時間取り組んでも解けず、少なくとも単純な問題でなかったことは分かる。Jは非常に巧妙で、方向性は見えるのに導出が苦しく、実装量も膨大だった。Petrは後のブログで、コードを書き終えたところで辞書順最小という条件を忘れていたことに気づき、そこで断念した、という趣旨の出来事を紹介している。

そして順位確定のリゾルブでは、劇的な大逆転が起きた。スコアボード凍結前、モスクワ大学は6問で大きくリードし、2位は4問だった。この難易度を考えれば、優勝はほぼ決まりに見えた。ところがサンクトペテルブルク大学が最後の1時間で3問を通し、同じ7問、ペナルティ39分差で逆転優勝した。最後の問題は8回の不正解のあと、大会終了2分前にAC。これ以上ないほどぎりぎりの逆転だった。

そんな話はさておき、僕たち三人はひどく落ち込んでいた。そして全員で、来年もう一度挑戦しようと決めた。

前年の成績があまりにもひどかったので、この年は本気で準備することにした。

チーム内の三人の役割は、すでにはっきり分かれていた。僕は実装系の問題と、いろいろ変わったアルゴリズムの担当。この一年で、半平面交差やACオートマトンなど、それまで名前すら聞いたことのなかったアルゴリズムを大量に覚えた。名前からしていかにも難しそうだが、実際よく使う。僕の練習方法は、過去の地区予選の問題をひたすら解くことだった。これなら、よく使うアルゴリズムをだいたい一通りカバーできる。

もう一人のコードを書くチームメイトは、数学、動的計画法、貪欲法などを担当した。とにかく数学が少しでも絡めば彼の仕事だ。彼はCodeforcesとTopcoderのコンテストに出て練習していた。この二つの問題はICPCとはかなりスタイルが違う。どの問題にも多少は数学が絡み、コンテスト時間の都合で実装量もあまり大きくできない。その分、数学寄りのアルゴリズムを学ぶにはちょうどよかった。

最後の一人は、まったくコードを書かず、変わった知識を広く集める担当だった。僕たちからの要求は、「実装できなくてもいい。でも何でも知っていてくれ」。彼はオンラインジャッジを開き、順番に問題を読んでいった。分からなければ解説を読み、見慣れない技法に出会ったら覚える。僕たちにも必要そうなら共有する。そういう練習だった。

個人練習だけでなく、チーム練習も前年とは比べものにならないほど増やした。大会に集中するため、最後の学期は三人とも履修を下限まで減らし、しかも楽な授業ばかり選んだ。僕と数学担当は修士1年、問題を読む担当は学部4年だった。最初は週1回、学期末が近づくと週2回、休みに入ってからは毎日1回。1回のコンテストだけで5時間かかり、そのあと解けるはずだった問題を全部復習して解き直すと、それだけで一日が終わる。それでも足りない日すらあった。

練習を重ねるうちに、僕たちの自信はどんどん膨らんでいった。Codeforcesで5時間のバーチャルコンテストをしていると、その年の世界大会に出るチームの多くが、同じセットを練習していることに気づいた。バーチャルなので開始時間は別々だ。清華大学、北京大学、上海交通大学、それにヨーロッパのチームとも何度も同じ問題で競った。たくさん参加すれば、強いチームにも調子の悪い日はある。つまり、僕たちは見かけた強豪のほぼすべてに、一度くらいは勝っていた。そこで出した結論は、「運と調子さえよければ、絶対に勝てない相手なんているのか？」。考えてみると、その年のtouristのチームくらいしか思い浮かばなかった。目標はメダルだった。

そして本番で分かったのは、「運と調子さえよければ」という条件が思った以上に厳しいことだった。実際の僕たちは、普段通りより少し悪い程度の出来だった。

もっと深刻な問題もあった。Codeforcesで練習したセットの大半はロシアの合宿コンテストだった。ロシアには非常に強いチームが多く、touristが所属するサンクトペテルブルクのITMO大学も、すでに何度も優勝していた。しかし、その合宿の問題は世界大会とかなりスタイルが違う。Codeforces本体に近く、数学の比重が高い一方で、実装量は少ない。簡単に言えば、その練習で鍛えられたのはほとんど数学担当だけで、僕の純粋な実装力はまるで伸びていなかった。残念ながら、それに気づいたのは大会後の反省会だった。

この年は選手三人、コーチ、そして前年ロシアへ行けなかった副コーチも一緒に飛行機でモロッコへ向かった。大会前の数日にあった観光イベントは、もうほとんど覚えていない。当時は頭の中が大会のことでいっぱいだったのだと思う。

覚えているのは、とにかく外が暑かったことだ。外へ出るだけでつらく、ずっと冷房の効いた部屋にいたかった。道で陽気な人に会うと、こちらが暑そうなのを見て、暑いな、と話しかけてくる。そのあと何かを延々と話していたが、僕にはまったく分からない。最後に遠くを指さして、「the great Sahara!」と言った。そこだけは聞き取れた。近くにサハラ砂漠があることを自慢していたのだろう。

特に印象に残っている出来事がある。ロシア出身の副コーチは、本当に怖いもの知らずだった。マラケシュ中心部の市場で、露店のタトゥー屋に出会った。なぜタトゥー屋が路上に店を出しているのかは聞かないでほしい。一目で怪しく、まともな商売には見えなかった。すると副コーチが突然、「腕に虎でも彫ろうかな」と言い出した。店の人に絵を描いてみろと言われ、彼が腕に描いたのは、デフォルメされた猫だった。

僕たち三人の考えは完全に一致していた。それ、本当に彫ったら腕は無事なのか……。結局、理由は分からないが、副コーチはタトゥーを入れなかった。最後には本人も、さすがに怪しいと気づいたのかもしれない。

市場では搾りたてのオレンジジュースも売っていた。その搾り機は、見るからに無駄が多い。まずオレンジを真ん中で切って二つの半球にし、片方を皮が下になるよう機械に置いて、手で押しつぶす。ジュースが出たら、その半分はもう終わり。目で見ても歩留まりが悪そうだった。ただし、ジュースは本当においしかった。無駄が多いぶん、皮はもちろん、果肉を包む薄皮までほとんど混ざらない。苦味がまったくなく、ひたすら甘かった。

それまで、こんな機械は見たことがなかった。ところが数年後、中国へ帰ったとき、空港で同じ方式をもう一度見かけた。今度は自動販売機そのものの完全自動版だ。お金を入れると、その場でオレンジを三つ切り、押しつぶしてジュースにする。ところが、その機械は精度が悪かったらしく、途中で止まり、僕のオレンジを一つ勝手に持っていった。出てきたジュースはコップの3分の2だけ。当然、文句を言う相手もいない。さらに数年後に中国へ戻ったときには、その機械はもう見かけなかった。材料費は高い、機械は壊れる、苦情は多いで、事業ごとなくなったのかもしれない。

話を戻そう。三人で、現地でもう一度模擬コンテストをするか相談したが、結局やめた。直前にそこまで苦労して練習しても、何の意味があるのか分からなかった。

そして本番当日。会場に着くと、風船が13色あった。つまり問題は13問。これも前例のない数だった。これだけあれば、一問くらいは信じられないほど簡単な、ほとんどボーナス問題があるはずだ。そして実際、その通りだった。

開始5分でAに正解が出た。読んでみると、やはりサービス問題だった。僕たちも追いかけ、11分でACした。

次の問題を探した。Bは幾何で、一目見て無理そうだったので即座に捨てた。FとMは実装問題で、それほど難しくはなさそうだが時間がかかる。Dは微積分が必要そうな数学問題に見えた。問題を読む担当は、Cが簡単なネットワークフローだと見抜いた。僕も確認して問題なさそうだったので、すぐ実装を始めた。

28分、29分、30分に、F、C、Dの正解が続けて出た。やはりCは簡単なネットワークフローだと確信した。35分で書き終えて提出。WA。気まずい。コードを2回読み直したが、間違いは見つからず、そのまま詰まってしまった。

そこで、問題を読む担当にCのデバッグを任せ、僕はFの実装を始め、数学担当はDの式を導き始めた。開始から1時間ほどで、Cに抜けているケースがあることを見つけてくれた。そのケースを追加してコードを直し、63分でACした。

Fは実装に30分以上かかり、さらにサンプルに合わせて20分ほどデバッグした。やはり実装力が足りなかった。93分で提出してWA。そのあとコードを印刷し、紙の上でデバッグを続けた。

数学担当はDを書き始めた。彼はそれまで幾何問題をほとんど実装したことがなかったので、円周率の定数は十分長く書くこと――僕は以前これで失敗していた――そして計算量を気にしなくていいところではdoubleではなく全部long doubleを使うこと、と伝えた。その間に僕はFのバグを見つけ、少しだけ端末を借りて修正し、102分でFを通した。

Dは112分、一発でACした。

これで4問。顔を上げてスコアボードを見ると、状況はすっかり変わっていた。39分、47分、53分にはL、J、Iの正解が出ており、115分と118分にはEとHも解かれた。この時点で、全体では9問に正解が出ていた。首位は、僕の記憶では東京大学で、すでに7問。2時間で7問も前例がなかった。以前聞いたカーネギーメロン大学のコーチの分析では、2時間で9問に正解が出る展開なら、メダルには10問、金メダルには12問が必要になる。

数学担当はLを読み始め、僕はIを実装した。Iは単純な区間マージの問題だった。複数の区間グループがあり、すべてのグループに覆われる部分の合計長を求める。最初に考えたのは線分木、それも端点が実数なので座標圧縮した線分木だった。ただ、すでに多くのチームが通しているのに、全員がそんなものを書いたのだろうか。どう考えても大げさだ。それでも世界大会ならあり得るか、と考え直した。結局、考えすぎだった。すべての空白部分を区間として扱えば、少なくとも一つの区間に覆われる長さを求める問題になる。それを全体の長さから引けばよく、ソート一回で終わる。

ところが僕たちは、会場で座標圧縮した線分木と格闘し始めた。正直、それ自体はそれほど複雑ではない。126分には最初のWAを出していた。ただ、この形では一度も書いたことがなく、境界条件や実数の等値判定など、間違えそうな場所はいくらでもあった。そこから長いデバッグが始まった。この大会で一番詰まり、最も時間を無駄にした問題だった。だいたい30分ごとに提出し、4回WA。269分でようやくACした。取りかかってから通すまで、3時間以上かかったと思う。

僕が紙の上でIをデバッグしている間、数学担当はLを書いた。それほど複雑な問題ではなく、173分で一発ACだった。

そして、この大会で最も不思議だったのがJだ。一見、数学問題だった。読み終えた数学担当が、「巨大な整数同士を高速に掛け算するアルゴリズム、何か知ってる？」と聞いた。僕たちは二人とも知らないと答えた。必要なのは高速フーリエ変換、FFTだった。練習ではFFTの問題に一度も出会わなかったので、誰も実装できない。数学担当は必要なアルゴリズムを正確に突き止め、足りないのはFFTだけだった。ではどうするか。表を埋め込んで提出しよう。

入力は整数一つだけなので、事前計算した表をコードに直接入れるにはぴったりだった。問い合わせは表を見て答えればいい。計算してみると、その表はどうにかソースに収まりそうだった。どの間隔で値を保存するかによって、ファイルサイズが変わる。100個ごとに一つ保存するなら、提出するプログラムは約100KB。ただし問い合わせがその間に来ると、実行時に最大100個分を計算する必要がある。50個ごとなら200KBになるが、計算は50個で済む。提出できるソースファイルの上限も知らなかったので、とにかく一度試すことにした。

こうして、巨大な表との長い戦いが始まった。本来なら、それほど面倒ではないはずだった。しかし大会用ノートPCの性能があまりにも低かった。100KBのファイルをチームメイトが保存しただけで固まり、危うくフリーズするところだった。カーソルが30秒も回り続けて、ようやく保存完了。毎回、今度こそ完全に止まるのではないかと怖かった。大量のデータを一度にコピー＆ペーストすると、また固まりそうなので、操作にも細心の注意が必要だった。普段なら、少し書くたびに保存するのはよい習慣だ。しかし今回は完全に負担だった。まだ変更が終わっていないのに、チームメイトが癖で保存のショートカットを押す。その直後には毎回、思わず悪態が出て、「なんでまた押したんだ」と自分の手を責める声が続いた。

その後の2時間は、僕が座標圧縮線分木を少し直し、チームメイトが巨大な表を少し直す、その繰り返しだった。交代で端末を使い、交代で提出し、交代でWAを出した。

スコアボード凍結前には、メダル圏の最低ラインがすでに8問になっていた。僕たちは2問に詰まったまま、どうすればいいか分からない。目標はメダルなので、新しい問題も開かなければならない。僕と数学担当が忙しい間に、問題を読む担当がEを調べ、簡単な貪欲法で解けそうだと言った。僕はすぐにその貪欲を書いたが、2回続けてWA。彼にもアルゴリズムが悪いのか、実装が悪いのか分からない。これで3問同時に詰まった。すると数学担当がちらっと見て、「この貪欲、絶対違うでしょ」と言い、30秒で反例を出した。Eは完全に分からなくなり、僕たちは再び2問だけに詰まった状態へ戻った。

表を埋め込んだJは、大会終了4分前の最後の提出で、どうにかACした。これで僕たちの大会は終わった。

一つだけ自慢できるのは、Jを表の埋め込みで解いたこと、そして会場でそれをやったのが僕たちだけだったことだ。公式の大会後解説にも、この問題は表を埋め込んで解くことができ、実際に会場で一チームがその方法を使った、とわざわざ書かれていた。その一チームが僕たちだった。

当時の僕は、もしかすると作問者も表を埋め込めるとは思っておらず、僕たちの提出を見て初めて気づき、その一節を解説に追加したのではないか、と考えた。それから10年後、自分がジャッジになり、当時の人たちと接し、問題準備に求められる基準も知った。今から考えると、ジャッジは最初からこの方法を分かっていて、それでも許可していた可能性が非常に高い。

最終成績は7問。ペナルティを無視すれば同率28位、ペナルティ込みではちょうど50位。7問を解いたチームの中では最下位だった。

大会後、僕たちはコーチに、「簡単な問題は全部解いたので、最低限の仕事はした」と話した。ただ、IとJにあまりにも長く詰まり、ほかの問題へ使う時間がまったく残らなかった。Iで考えすぎず、JでFFTを使えていれば、それぞれ少なくとも1時間は節約できた。その時間があれば、純粋な実装問題のMは解けたかもしれない。純粋な数学問題のHも、数学担当ならかなり可能性があったと思う。

でも現実に「もし」はない。少し悔いが残った、としか言えない。tourist率いるITMOチームは全問を解き、満点で優勝し、時間内に全完して早く退場するという偉業を達成した。世界大会でそれを成し遂げた史上初、そして今も唯一のチームだ。順位確定のリゾルブでは会場中が沸き上がった。誰もが伝説の瞬間を見たかったのだと思う。

一人の選手がICPC世界大会に出場できるのは、最大2回まで。これで僕のICPC選手としてのキャリアは正式に終わった。

この年の世界大会の開催地には、かなりがっかりした。もう選手ではないので、世界大会へ行っても基本的には観光して、試合を見て、イベントを楽しむだけだ。だから当然、どうせなら旅行先として魅力のある場所で開いてほしい。前年のタイ・プーケットはよかった。今年はというと……この場所を前から知っていた人、全員手を挙げてみてほしい。実際にマウント・ラシュモアへ行ったことがなければ、ここにあると誰が知っていただろう。

今回の旅費は大学持ち。これだけで気分がいい。一つだけ残念だったのは、その夏は大学で研究をしていて、本来なら受講者の多い授業のTAをして、当時の僕にとってはかなりの大金を稼げるはずだったことだ。ところが担当教員に相談すると、その授業のTAは一人しかいないので、いきなり一週間休む人は採れないと言われ、断られた。仕方なく別の小さな授業のTAになり、もらえる金額は半分になった。でも迷う余地はない。世界大会へ行くほうが絶対に大事だ。

この年の大学チームは、僕が「アメリカ人兄弟」と「香港記者」と呼んでいた三人だった。どうやって予選を勝ち抜いたのか、そしてなぜそんな呼び名なのかは、いつか書く予選総集編を参照してほしい。

今回はようやく、落ち着いた気持ちで一日観光に参加できた。主催者が連れて行ってくれたのは、この辺りで一番有名なマウント・ラシュモア。僕は香港記者と一緒に回った。さすが香港記者、目ざとい。なんと一人で歩いているtouristを一瞬で見つけた。少し迷ったあと、迷いを振り切って突撃し、写真をお願いして、無事に撮影成功。香港記者はずっとtouristの大ファンだったので、これは大勝利だ。写真を撮り終えると、touristはまるでゲームの瞬間移動とダッシュを同時に使ったような速さで消えた。これ以上ほかの人に捕まって写真を頼まれたくなかったのだろう。僕は撮れなかった。大損だ！

というわけで、ここには代わりに岩肌むき出しのマウント・ラシュモアを載せておく。当時の自分の写真を見ると、まだ若かったのに、もうこんなに若かったとは驚きだ。

その次は、クレイジー・ホース記念碑を見学した。これは何と言えばいいのか。確かに彫刻ではある。僕が聞いた話では、由来はだいたいこうだった。4人の大統領像が完成したあと、先住民の酋長が納得せず、「自分たちにも偉大な英雄がいる。そちらの大統領像より大きな像を彫る」と言ったという。完成予定の像は高さ172メートル、幅195メートル。楽山大仏の2倍以上で、馬の頭だけでも4人の大統領の頭より5メートル以上高い。完成すれば世界最大の人工彫刻になる。1948年に始まってから60年以上、酋長と7人の息子たちはまさに少しずつ山を削り続けてきたが、完成したのはクレイジー・ホースの顔だけだった。話によると、この計画に関わる人たちはアメリカ政府の資金を受け取らず、自分たちの民族的英雄の像を独力で完成させたいと考え、すべて民間の寄付で進めている。そのため資金が足りないらしい。

今の完成度はというと……写真の通りだ。手前にあるのは売店前に置かれた完成予想模型、遠くの山が実際の進み具合。この完成度、本当に10％もある？

大会当日になっても、僕にはまったくプレッシャーがなかった。選手たちにも、あまり緊張はなさそうだった。自分たちの実力は本人たちが一番分かっている。世界大会で正式な順位さえつけばいい。順位のつかないHonorable Mentionでなければ、それで十分だった。

ところが結局、Honorable Mentionになった。三人は63分で3問を通したあと、残りの4時間は取り組み続けたものの、新しいACは一つも増えなかった。そしてITMOは、今回も何の意外性もなく優勝した。

会場での僕は何もすることがなく、知り合いもいなかったので、ひたすら歩き回っていた。そのうち、上海交通大学関係者の小さな観戦グループを見つけ、かなり長い間、その後ろに座って問題の議論を聞いていた。正直、5時間は長いと思っていたが、時間は驚くほど早く過ぎた。何の変化もないスコアボードをぼんやり眺め、自分でも何を見ているのか分からないことがあった。それでも見ているうちに、2時間が消えていた。

大会終了後、夜になると、主催者が山を背景にした「ライトショー」へ連れて行ってくれた。わざわざかぎ括弧をつけたのは、これをライトショーと呼ぶのか？ と言いたいからだ。山の中で適当に100人集めてレーザーポインターを持たせれば、同じくらいのものができるのでは？ あまりにもショボかった。派手な光と音の演出をよく見る中国人の僕だから物足りなかった、というだけでもない。同じチームのアメリカ人コーチまで、何とも言えない顔になり、途中で会場を出ていった。その様子は、まるでこのショーがアメリカの恥だとでも思っているようだった。