アスタナ

この年の9月も、年に一度の世界大会に参加した。今年三度目である。本来なら今年一度、去年二度のはずだったのだが、エジプト大会まで今年に移ってきたのだから仕方がない。

ジャッジとして世界大会に参加するのは、これで三回目。前よりずっと落ち着いていて、もう日常行事のような気分になっていた。

当時、カザフスタンは中国国籍者に対してビザなし入国を認めていた。今回は今までで一番スムーズだろうと思っていたら、国際線がまたしっかり勉強させてくれた。

もともと買っていたのは、Lufthansaの往復便だった。サンフランシスコからフランクフルトで乗り継ぎ、そのままアスタナへ向かう。ただ一つ気になったのが、フランクフルトで空港内の電車に乗ってターミナルを移動する必要があり、その時に入国が必要なのか分からなかったことだ。これほど大きな国際ハブなら、国際線乗り継ぎエリアは完全に分離され、電車も自由に使えるはず。そう思って航空会社と空港の公式サイトを隅々まで見たが、「絶対に大丈夫」と断言できる説明は見つからなかった。読んだ限りでは、独立した「国際線乗り継ぎエリア」があり、そこから出なければ入国は不要、という意味に見える。最後まで確信は持てなかったが、信じることにした。

ところが、もっと大きなトラブルはそのあとだった。出発の三週間前、帰りのアスタナ発フランクフルト行きが欠航になった。これで旅程全体が使えなくなる。普通なら別の時間の便へ振り替えればいい。でも、その日はその一便しかない。翌日の便にすると、その先のフランクフルト発アメリカ行きも一日おきなので、フランクフルト空港に24時間以上滞在することになる。さすがに無理だった。

このルートはもう使えず、全部取り直すしかない。料金は全額返ってきたが、とにかく面倒だし、出発日が近づけば航空券はだいたい高くなる。調べ直してみると、僕のパスポートとビザの状況では、ヨーロッパ経由に使える便が見つからなかった。イギリス経由は空港を移動する必要がある。当然、僕はイギリスのビザを持っていない。ポーランド経由はワルシャワ空港で20時間待ち、しかも前後が別の航空会社。入国が必要か分からないが、当然シェンゲンビザもない。航空券を見ているだけで気が滅入ってきた。イスタンブール経由など時間のいい便もあったが、直前すぎてもう残っていなかった。

どうする。もう行けないのか？

いったん冷静になって考えると、アスタナとサンフランシスコの時差はちょうど12時間ほど。なら、逆方向もありでは？　そこで東回りで世界を一周する便を探してみた。すると、ちゃんとあった。最適な場所は中国での「乗り継ぎ」だった。Googleの検索結果にはまったく出てこない。そもそもこれは乗り継ぎですらないからだ。別々の航空券なので、おそらく一度入国する必要がある。僕はアメリカ―中国往復と、中国―カザフスタン往復を別々に検索した。すると時間が見事に合う。中国への入国なら僕には何の問題もない。その場で決め、すぐ予約した。

北京空港に命を救われた。これがなければ、今回の世界大会には行けなかったと思う。

こうして苦労の末、ようやくアスタナへ到着した。ほかの人と話してみると、あの欠航便を予約していた人はかなり多く、みんな取り直していた。ただ、アメリカのパスポートならヨーロッパでの乗り継ぎはずっと楽で、僕ほど面倒なことにはなっていなかった。

今年の新しい出来事といえば、Codeforces世界ランキング1位だったGennady Korotkevich、つまりtouristがジャッジ陣に加わったことだろう。ジャッジに必要なのは問題を解ける強さであって、「速く」解く強さではない。そのため、オンラインコンテストに出ないジャッジもいれば、レーティングがそれほど高くないジャッジもいる。すると、ジャッジがフォーラムで大会中の状況を説明していても、「で、あなた誰？」と聞かれることがたまにある。これからはもう、その心配はなさそうだった。

もう一つ、今年は初めてAIで問題のイラストを作った。仕上がりはかなりよかった。

大会の数日前、忙しい合間に一日だけ時間を作り、アスタナ観光へ出かけた。といっても、主に歩いてアスタナ・グランド・モスクへ行っただけだ。

ネットの写真と本当にまったく同じだった。内部は非常に精巧に造られている。人が一人も写っていない写真を撮るのも、なかなか大変だった。

歩いて戻る途中、街中でこういうポスターをたくさん見かけた。文字は読めないが、絵を見る限り、カザフスタンの伝統スポーツ大会らしい。素朴な疑問なのだが、鷹を調教するのも競技なのだろうか？

今回の世界大会の開会式は、大統領センターのメインホールで行われた。警備は空港並みに厳しい。ほぼすべてのバッグを開けて確認するため、運営からのおすすめは「バッグを持ってこないこと」だった。ただ、日程上、それまでのイベントに参加した選手は、コーチに預けてホテルへ持ち帰ってもらわない限り、バッグを持たずに来るのは難しい。結局、多くの人がバッグを持ってきた。

僕は前のイベントにまったく参加していなかったので、かなり早く着いた。会場にはまだ誰もおらず、歓迎演奏のバンドだけがいた。

そのあと、選手たちが次々とバッグを持ってやって来るのを眺めていた。保安検査は一時間たっても終わらなかった。

開会式については省略する。何度参加したか分からないくらいなので、結局どれも似たような内容に見えてくる。

本番の前日には、運営主催の見学イベントもあった。行き先は科学館のような施設。外から見るとこんな感じで、球形の建物の中が何層にも分かれているのが見える。まずエレベーターで最上階へ上がり、展示を見ながら一階ずつ下りていく方式だった。

館内の説明文は、ほとんどがカザフ語、ロシア語、英語の三言語。スタッフにも三言語を話せる人が多く、かなりすごい。ここで昔の大学の副コーチに会った。彼はロシア語が分かる。僕は、ロシア語とカザフ語はどれくらい違うのか聞いてみた。僕には文字が似て見えた。どちらも読めないから、そう見えただけかもしれない。彼によると、かなり違う完全に別の言語で、自分にはカザフ語は読めないとのことだった。

大会会場はこんな感じだった。

会場内には、遊べる設備や技術展示がたくさん用意されていた。これも昔からの伝統だ。大会前後は選手が暇な時に遊び、本番中はコーチや関係者が遊ぶ。ホテルの下には、ゲルのようなスペースまであり、中はこんな感じだった。

暇な時にここで横になったら、そのまま一日過ごせそうで、なかなか気持ちよさそうだった。

ここまで来れば大会も順調に進むと思っていた。ところが最大の事件は、競技前日の夜に起きた。

その夜、ホテルでシャワーを浴び、もう寝る準備をしていた。シャワー中に電話が三回来ていたが、全部出られなかった。終わって確認すると、「大変なことになった。問題に不具合がある。すぐ来て」とのこと。僕が呼ばれたのは、その問題の作成者だったからだ。どの問題かは言わない。全問題を知っている読者なら、自分で推測できるかもしれない。

発端はこうだった。通常、競技前日に問題を実況解説者へ共有し、内容と解法を先に把握してもらう。事前に解説動画を収録できるし、本番中もより詳しく分析できるからだ。この問題の解法は、最初に場合分けを行い、貪欲法によって二つのケースだけを考えるものだった。ところが解説を収録しているうちに、どうもおかしいという話になった。「なぜ二つだけなんだ？」

そこで厳密に確認するため、誰かが全パターンを列挙して最適解を求める総当たりプログラムを書いた。その結果が、公式データの答えと一致しなかった。総当たりのほうがさらに良い解を見つけていた。

終わった。全列挙が正しいに決まっている。公式データが間違っていて、リファレンス実装も全部間違っている。

この時点でもう午後9時近く。競技開始まで約12時間だった。すぐに応援が呼ばれ、僕たちも大勢が下へ集められた。そして分かった。この問題、本当に間違えやすい。解いた人全員が、別のケースを当然のように見落としていた。しかも全員が独立に、同じように思い込んでいた。

中心メンバーが考えていたのは、今の状態からどう問題を直せばすぐ救えるか。残りの僕たちが考えていたのは、問題文を変えずに救えないか、だった。

以前の世界大会でも、似た出来事があった。当時の僕はジャッジではなく、あとから公式の大会後分析を読んで知った。その説明によると、競技前夜、ある問題が完全に間違っていて修正不可能だと判明した。しかし問題冊子はすでに印刷され、ホチキス留めされ、封までされていた。そこでその夜、全冊子の封を開け、ホチキスの針を外し、間違った問題を抜き、別の正しい問題を入れ、もう一度留めて封をし直したらしい。作業はほぼ一晩中続き、最後には全員がホチキス外しの達人になっていたそうだ。

今回は、そこまで深刻ではなさそうだった。見落としたケースが有効なのは、特定の入力範囲だけ。制約を半分にすれば、そのケースを考える必要は完全になくなる。しかも元の制約の書き方なら、数字を半分にしても、問題そのものの誤りではなく単純な印刷ミスの訂正にしか見えない。会場全体に一度案内するだけで、大会を混乱させずに問題を修正できる。

中心メンバーは関係者へ次々に電話し、翌朝この対応が必要になるかもしれないので準備してほしい、と連絡していた。

その間、残った僕たちは、問題を変えずに何とかできないか話し合っていた。すると、本当に何とかなりそうだと分かった。確かにケースを見落としていたが、どうやら一つだけ。つまり、それを追加しても解法の計算量は変わらない。そこで何人かがプログラムの修正を始めた。この時点でもう午後10時だった。

20分後、最初の一人が修正を終えた。さらに5分後、僕も完成した。その後も次々と実装ができ、中には最初から全部書き直した人もいた。各プログラムを突き合わせると問題なし。さらに総当たりプログラムで作ったデータでも試し、やはり一致した。これで正しい解法を得られた。危機は無事に乗り越えた。

そのあとは、新しいリファレンス実装ですべてのデータを再実行し、新しいケースに合わせてテストも大量に追加した。全部終わった時には午後11時半。よかったのは、案内を出す必要がなく、問題文も一切変えずに済み、本番へ何の影響も出なかったこと。悪かったのは、この問題がかなり難しくなったことだ。このケースは本当に思いつきにくい。本番で不正解になっても、実装のバグなのか、ケースを見落としたのか判断しにくい。必要なら、貴重なコンピューター時間――三人で一台しか使えない――を使って総当たりを書き、照合することになる。

そして翌日。競技は予定どおり始まった。作問者として見ていると、この問題は最初に想像していたよりはるかに難しいらしい。最後の追加ケースはひとまず置いておいて、普通なら多くのチームが提出し、そのケースで落ちると思っていた。現実には、そもそも提出すらほとんど来ない。正解が出たのは三時間後で、全体でもトップ3に入る難問になった。

僕たちはこの問題への提出を一つずつ注意深く見ていた。当時、初回提出したすべてのチームがあのケースを見落としており、一発で通ったチームは一つもなかった。やはり、とんでもなく間違えやすい問題だった。

逆に言えば、前夜にこのケースを発見していなくても、大会はたぶん普通に進んでいた。誰も気づかず、影響を受けるチームもいなかっただろう。最初の不正解を受ける前に、そのケースへ気づいたチームが一つもなかったからだ。ずっとあとになってデータが公開されてから、ようやく誰かが掘り返しに来たかもしれない。

競技中、暇になったジャッジが問題をAIに解かせていた。僕の記憶が正しければ、完全なプログラムを書いてそのまま正解できたのは二問か三問ほどで、しかも最も簡単な問題ではなかった。この頃のAIの競技プログラミング能力は、まだ強かったり弱かったりで安定せず、さらに伸びる必要がありそうだった。それが、わずか一年後にはICPC形式の問題セットを丸ごと解くようになるなんて、誰が想像できただろう。

最後に、北京大学の再びの優勝、おめでとう！　ペナルティで約300も差をつけたのは、さすがの強さだった。

一番惜しかったのは清華大学だ。初の世界一まで、あとテストケース一つだった。外から順位表だけを見れば、二問で不正解が出ていて惜しかった、くらいに見える。でもジャッジ側からは、そのうち一問が最後のテストケース一つだけで落ちていたことが分かった。何度見ても、そのデータに特別なところは見当たらない。それでも最後まで原因を見つけられなかった。あの失敗の原因を直して通していれば、もう一問多く解いて、そのまま優勝だった。本当に、あと一歩だった。