ロシア

初めての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。これ以上ないほどぎりぎりの逆転だった。

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