モロッコ

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

チーム内の三人の役割は、すでにはっきり分かれていた。僕は実装系の問題と、いろいろ変わったアルゴリズムの担当。この一年で、半平面交差や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選手としてのキャリアは正式に終わった。