__________の ICPCアジア地区予選2011参戦記 No.2/3

1:54経過 【__________(ノーネーム)】 ABF 3/10完

「ちっ。WA(Wrong Answer)ったか」
 ぐしゃぐしゃと髪をかき回す。
 くそっ。カズミの奴は、もうABCFGの5完だってのに……。

 とはいえ、ここで焦っても仕方ない。
 絶対にバグを出さないなんて、一部の人外を除けば普通のプログラマーにはまず不可能。
 肝心なのは、バグを出してしまったときに、いかに速やかに対処するかだ。
 このままパソコンを使ってデバッグする手もあるが、サンプルは通っていてWAの原因が推定できていない以上、ここはいったん手を引くのが最善だろう。

 それに、うちのチームには、こんなときのための秘密兵器がいるわけだしね。

「トウコ。いつものやつ、任せたわよ」
「いぇっさー」
 バグの入ったD問題のソースコードを印刷して、トウコに渡す。
 普通なら、この紙をじっと睨んで隠れたバグを探すのかと思うでしょうけど、そうじゃない。
 トウコは、無表情な瞳で、じっとプログラムを見つめていたかと思うと、唐突に、

 ぴりぴり、と。

 紙の上端を細長く切り取るように指で破り、そして、

 ぱくり、と。

 食べた。

 ……うん。何を言っているのかわからねーと思うから、今から説明する。

 トウコは、ソースコードが印刷された紙を、(比喩ではなく)「食べる」ことで、バグの有無や種類を判別することができる。
 ちなみにこれは、強豪プログラマーの多くが持っている“能力(スキル)”でもなければ、努力で身につけることができるような“技術”でもない。
 ぶっちゃけあたしも、こいつがこんなことをできる理由も原理もまるで理解しちゃいないんだけど、とにかくトウコには、そういう得体の知らない“力”がある(本人に訊いても、「……気合と経験?」などと首を傾げてやがったので、たぶん自分でも分かってない)。
 無論、原理なんて分からずとも、できる以上は存分に利用させてもらう。
 あたしたちがリスク覚悟で完全分業体制を実行に移せているのは、もしバグを出したとしてもトウコがいるという安心感によるところが大きい。

「んぐ。のどごし爽快。バグはない」
 紙の上に印刷されたソースコードを、数行ずつまとめて手で破ってから、むしゃむしゃ食べる。
 これが、バグのある箇所だと、喉に詰まる感じがするらしい。
 また、「のどごし」の違いで、そのバグがWA(Wrong Answer)になるのかRE(Runtime Error)になるのかTLE(Time Limit Exceeded)になるのか分かったりもするんだとか。
 この説明も光景も何もかもシュールなのだが、もう慣れた。

「もぐもぐ。うまい。バグなし」
 本人いわく、コードの食べ心地の見極めは繊細な作業らしいので、1つのコードをデバッグするのには、コードの長さにもよるが、普通10分から数十分と、無視できない時間がかかる。
 これをやっている間、トウコは問題を解けなくなるわけで、あまり乱用できる手ではないものの、それでも有限の時間でバグが取れることが保証されているのは大きい。

 ちなみにあたしたちは、この技のことを“食道デバッグ”と呼んでいる。
 そしたらいつの間にか、トウコは“貪欲戦車(グスタフ・マックス)”なんていう二つ名で呼ばれるようになっていた。
 本人はこの名を悪く思っていないらしく、食道デバッグの様子を見た誰かによってつけられた異名だと主張してはいるけれど、おそらくはいつ見ても何か食ってるトウコに呆れはててつけた名前なんだろう。間違いない。

 閑話休題

 Dのデバッグはトウコに任せておけばいいとして、次は。
「タマキ。今すぐに解き始められる問題、何かある?」
 残念ながら、あたしには今すぐパソコンを使ってできることは何もない。
 代わりに、今まで待機していたタマキに、現状を訊ねる。
「I問題なら、たぶん時間があれば解けるとは思うけど……」
 Iか。たしかブレインネクサスが序盤に速攻で通してたわね。
 幾何問題か。確かにタマキが得意なジャンルではある。
 だけど。
「これ、おそらく実装かなり面倒臭いわよ。まだ5問目だし、他に何か……」
 ないの? と口を出そうとしたところで、タマキに割り込まれる。
「うん、それでねサクヤちゃん。さっき気づいたんだけど、このE問題なんて面白そうじゃない?」
「E……?」
 順位表を見上げる。E問題は、まだ誰一人として通していない。
「どんな問題なのよ……ってこれ、まさか!」

 三角格子の上を、正二十面体が転がっている図。
 1つ1つの面にユニークな番号が振られた、正二十面体の展開図。
 そして、問題文の端々から察するに、これは……。

「たぶん、(0,0)に0番の面が接している状態からスタートして、正二十面体を転がしていって、ゴールの(X,Y)にn番の面が接している状態にするまでの最短手数を求めなさい、って問題だと思う」
「超っ絶に面倒臭いじゃないの……本質とは全然関係のないところで……」
 幅優先探索を、するだけ。
 でも、そのStraightforwardな段階に達するまでに、無駄に大きな壁がある。
「おそらく、この図を切り取って、実際に組み立ててみましょうって問題よね。これはこれで、相当面倒くさい……って、あ、そういえば、あんた」
 ふと気づく。
 タマキは、コンテストの度に、お守りとして趣味の色々な形をしたダイスを持ち込んでいたことに。
「そうか……。正二十面体のブランクダイスを使えば……!」
 工作の手間が、大幅に省ける。

「よしタマキ! GO!」
「了解だよっ! サクヤちゃん!」
 嬉々として、空いたパソコンの前に座るタマキ。
 タマキに任せておけば、この問題は解けたも同然だろう。
 ……って、あれ?
「ねえタマキ。でも結局、正二十面体の面の推移関係を求める段階では、パソコン使わないんじゃ――――」
 まずは、紙の上で、これを打ち込めばいいって段階まで固めてから――――。
 そう言おうとしたけれど、その言葉は途中で呑み込まざるを得なかった。

「5,1,4! 6,2,0! 7,3,1! 8,4,2! 9,0,3! 0,10,11! 1,11,12! 2,12,13! 3,13,14! 4,14,10! 5,9,15! 6,5,16! 7,6,17! 8,7,18! 9,8,19! 10,19,16! 11,15,17! 12,16,18! 13,17,19! 14,18,15! できたっ!」

 またたく間に、魔法の配列(マジックアレイ)は完成した。

int dx[2][3]={{0,-1,1},{0,1,-1}};
int dy[2][3]={{1,0,0},{-1,0,0}};

int adj[20][3]=
  {
    {5,1,4},
    {6,2,0},
    {7,3,1},
    {8,4,2},
    {9,0,3},
    {0,10,11},
    {1,11,12},
    {2,12,13},
    {3,13,14},
    {4,14,10},
    {5,9,15},
    {6,5,16},
    {7,6,17},
    {8,7,18},
    {9,8,19},
    {10,19,16},
    {11,15,17},
    {12,16,18},
    {13,17,19},
    {14,18,15},
  };

 様々なダイスが詰め込まれたタッパーは、結局一度も開かれることはなかった。

「タマキ……あんたこれ、全部今の一瞬で、脳内で?」
「ん、どうしたのサクヤちゃん? だってここに展開図と面の番号が書いてあるから、これを組み立てた通りに打ち込むだけだよ?」
 当たり前のことをやっただけなのに、と不思議そうに首を傾げる。
 そんな愛くるしい表情のタマキに向かって、あたしは。
「タマキ偉いぞよくやったっっ!!」
「わ、わ、サクヤちゃん。どうしたの、急にっ!」
 顔を赤らめるタマキを、思いっきり抱きしめる。
 もう……っ。最高だよ、あんた!


 10分後。

「よーしっ! 幅優先探索終わりっ! サブミット!」
 ジャッジにEのコードが転送され、即座に結果が返ってくる。

 Yes - Accepted.

 グレーの風船が打ち上がり、4完。
 そして、同時に。

「んぐぅ。サクヤ、この行、喉に詰まって食べにくい」
 トウコが指さす、半分くらい食べかけの行に書かれている文字列は。

vector<pair<int, int> > adj[3010];

「なるほどそこかぁっ! トウコ、サンキュ!」
 道の上限は3000本でも、街の上限は6000個!
 そりゃあWrong Answerするわけだよ!

 3を6に書き換えて、サブミット。

 Yes - Accepted.

「よっしゃあっ! これで一気に5完!」

 経過時間は2:15。
 ちょっと手間取りはしたけど、悪くないタイムだ。


「ねえサクヤちゃん。このDのソースコードだけど、なんでわざわざ、コード量の多いこっちの解法で書いたの?」
「ん。ああ、そのこと? まあ、色々思うところがあってね」

Problem D : Long Distance Taxi

 (与えられる数値はすべて整数である)

 いくつかの街と、街と街を結ぶN本の道(1<=N<=3000)からなる無向グラフが与えられ、それぞれの道には長さd_iが定義されている(1<=d_i<=2000)。
 容量Cのガソリンタンクを積んだ車が(1<=C<=200)、スタートの街(Given)から出発してゴールの街(Given)を目指す。
 スタート直後はガソリンは満タンで、長さ1だけ走るたびに0.1ずつガソリンを消費する。
 このグラフの中でM個(1<=M<=300)の街(Given)にはガソリンスタンドがあり、その街に着くと車のガソリンを満タンまで補給することができる。
 このとき、ガソリンの残量が0未満にならないようにゴールの街へと辿りつく際の最短走行距離を出力せよ。そのような走行ルートが存在しない場合は-1を出力せよ。

 N≦3000に対してM≦300であることから察するに、おそらくこの問題の作為解は、「ガソリンスタンドの存在する街を始点としたダイクストラ法を計M回行い、最後にガソリンスタンドのある街だけをノードとしたグラフ上でスタートからゴールへの最短路問題を解く(ちなみにここでワーシャルフロイド法を利用できる)」だろう。
 要するに、ガソリンという概念がなかった場合の問題に帰着して考えるわけだ。

 しかし、ガソリンの残量の取りうる値が高々2001通りの離散値しかないことを利用すると、(車が今いる街,ガソリンの残量)を状態に持ったよくあるダイクストラ一発で解くこともできる(この際の状態数は、約6000×2000に見えるが、スタートから辿りつける街は高々3000個しかないので、実は約3000×2000)。

 前者の解法は、まず制限時間を超過する危険性はないだろうけど、後者の解法は、もしかするとTLEするかもしれない微妙なラインだ。
 とはいえ、日本の審判団(ジャッジ)が用意するテストケースは、例年あまり強くないので、おそらく600万近い全状態を網羅するケースは含まれておらず、後者の解法でも余裕で通るだろう。もしかすると、後者の方が早い可能性だって十分ありうる。

 だとすれば、実装が楽で、早く書ける後者の解法を選ぶべきではなかったのか。
 タマキは、こう言いたいのだろう。
 もちろんあたしも、そんなことは分かっている。
 それでも前者の解法を選んだ理由は、用意されたテストケースが万が一強かった場合を恐れた、というのも無くはないんだけれど――――。

「<二重能力(ミメーシス)>対策、かしらね」
「????」
 タマキの頭の中に、疑問符がいっぱい浮かんでいるだろうことが、目で見ても分かる。
 ごめんね。今は説明できないの。あんた、人に物事を隠すのとか苦手そうだし。

「詳しくは後で教えてあげるわ。さ、2人とも、これからやることを話すわよ」
 DのデバッグとEのコーディングが行われている間に、あたしは今後の方針を決めていた。
 タマキとトウコに出す指示も、できる限り固めてある。

 チームの力を最大限に引き出す戦略を練るのが、リーダーの役目だ。
 みんな、お願い。あたしについてきて。



 必ず、カズミの野郎をぶっ倒してみせるから。



2:21経過 【玉兎(たまうさぎ)】 ABCDFG 6/10完

「ノーネームがE問題を14分で提出、か。ふふ。あそこのチームには渡部タマキが居るからね」
 相手の動きは手に取るように分かるとばかりに、緋笠カズミはくつくつと笑う。
「他のチームが必死に展開図を組み立てている中で、唯一正二十面ダイスをコンテスト会場に持ち込んでいた奇特な彼女らはといえば、そのダイスを取り出して眺めることすらしなかった、か。……やはり、君達のチームは面白いな、秋葉サクヤ」
 横目でノーネームの机を観察しながら、告げる。
「見事なファインプレーだった。素直に拍手を送ろう。……けど、残念だな」
 言葉とは裏腹に、不敵な笑みを浮かべながら。
「その程度の奇跡では、決して私には届かない」
 提出(サブミット)ボタンを、押し込んだ。

 Yes - Accepted.

 玉兎の机に、グレーの風船が上がる。

 ABCDEFG 7/10完。

 E問題を解くのに要した時間は、13分。
 <解法解放(ヘウレカ)>があれば、正二重面体の回転をシミュレーションすることなど、造作もない。
 タマキがあれほどの快挙を成し遂げてもなお、カズミには及ばない。

 3位の3完チームに2完差をつけて圧倒しているノーネームにすら、さらに2完差をつけて独走する、チーム【玉兎】。
 2つの能力(スキル)を持つ赤白(ターゲット)コーダー、緋笠カズミは、実に楽しそうに呟いた。



「さあ、ラストスパートだ。終盤戦の開始と行こうじゃないか」



3:52経過 【__________(ノーネーム)】 ABDEF 5/10完

「よし。J問題、Accepted」
 紫の風船が打ち上がる。これでようやく6完だ。

 J問題は、アジア地区予選には珍しい、高度なアルゴリズムを考えさせる良問だった。
 とはいえ、「同じ高さにある街は高々10個です」という露骨な条件があったおかげで、10を2の肩に乗せるという発想に至るのは比較的簡単だった。

 すでに残り80分を割っている状態で6完というこの現状だけを見れば、あまり芳しくない状況である。
 でも、そうじゃない。
 今、ノーネームの水面下では、いくつもの作業が並行して動いている。

「タマキ、トウコ。完全分業体制は終わり。今からあたしの言う指示に、従って」
 5完した直後、あたしは2人に向かってそう言った。
 このまま真っ当に闘っていても、カズミには勝てない。
 だからこそ、策を練る。
 完数の期待値を下げてでも、優勝する確率を最大化するために動く。
 カズミが玉兎を名乗るなら、あたしたちは金烏になって、あんたの積み上げてきたものを焼き尽くしてやる。

「んぐ。デバッグ完了。2つのコードのバグは、あらかじめ全て取りきった」
「サクヤちゃーん! Iの実装、紙の上で詰めておいたよー」
「サンキュ2人とも。次、トウコは手動でさっき言ったテストケースの作成、タマキはそのままIのコーディングに入って」
「いぇあー」「分かったよっ!」
 休む間もなく、次の指示を飛ばす。
 もう残り時間も少ない。間に合うかどうかギリギリだから、死ぬ気で働いてもらうしかない。
 幸い、今のところ、2人はあたしの言いつけたタスクを、大きなバグを出すこともなく的確にこなしてくれている。こちらは、このまま行けばおそらく問題ないだろう。

 不安が残るとすれば、それはあたしだ。
 なにせ、こんなこと、今までどのコンテストでだって経験がない。
 成功するかどうかは賭けだと言っていい。失敗すれば、もう後がない。
 それでも必死に知恵を絞って、少しでも成功確率を上げるために、想像する。予測しきる。

 あたしたちの思惑、カズミの思惑。


 そして、審判団(ジャッジ)の行動を。





 そして、30分後。

「さ……。行くわよ」
 提出(サブミット)ボタンを、押し込む。
 少し遅れて、もう1回。
 これで、CとGのコードが、ジャッジのもとへと送られていったことになる。

 結果は。

 No - Wrong Answer.
 No - Wrong Answer.

 ……ふう。

 予想通り、WAをもらう。これで、どちらの問題も、通算3回目のWrong Answerだ。

「そろそろいいかしらね。オペレーションRJ、フェイズ2に以降するわ」
 呟いて、汗をぬぐう。
 それにしても、今回はやけに故意のWAに縁があるというか何というか。
 とはいえ、今回の作戦は、最強最速の双子を相手にしたときとはわけが違う。
 相手の反応を伺うことができない中で、それでも繊細な進行が要求される。

「……ねえ。サクヤちゃん。わたしたち、さっきから一体何をやってるの?」
 タマキが、分からないなりにもこの場に漂う緊張感のようなものは伝わっているらしく、おずおずと訊ねてくる。
 万が一カズミの奴にでも察せられたら厄介だから、隠し事がすぐに表情に出そうなタマキには黙っていたんだけど、まあ、少しずつ説明していきましょうか。
「さっきから、10分くらいの間隔を開けて、何度もCとGのコードを送信しているでしょ? あれは、バレないように少しずつ内容を書き変えているとはいえ、基本的にやっていることは全部同じ。あたしたちが送っているのは、特定番目のテストケースだけ、わざと間違った答えを返すプログラム」
 WAになって当然。むしろ、WAになってくれなければ困る。
 ちなみに、送ったソースコードが確実に意図した挙動をしてくれることは、トウコの“食道デバッグ”で念入りに確認済みだ。
「? そんなことして、何かいいことあるの?」
「直接的にはないわ。けど、審判団(ジャッジ)の注目を、あたしたちのCとGに集めることができる」
 意外と知られていないことだが、ICPCのジャッジは、全自動で行われているわけではない。
 参加者からサブミットされたコードをコンパイル、実行するところまでは自動的に進むが、そうして出た結果(Accepted、Wrong Answer、Time Limit Exceededなど)が順位表に反映されるためには、必ず1人以上のジャッジが目視で承認をしてやる必要があるのだ。
 悪意のあるクラッキングなんかを防ぐための処置なんでしょうけど、今回はそれを利用させてもらう。
 ジャッジといえど、あくまでも人間だ。そこには感情があるし、心が揺れ動きもする。
 1位の玉兎には大差をつけられているとはいえ、2位のあたしたちノーネームが、何度も何度もCとGを提出し、その度にたった1つのテストケースでだけWrong Answerを出しているとなれば、動揺しないわけがない。

 すなわち、自分たちの作成したテストケースが、間違っているのではないか、と。

「よっぽど特殊なコーナーケースでもない限り、たった1つのケースだけ落ち続けるなんてこと、あんまり無いからね。まさか、あたしたちが意図的に間違った回答を出力するプログラムを書いているなんて、考えもしない」
 万が一ジャッジに提出したソースコードを読まれても大丈夫なように、タマキとトウコには、CとGのコードはできる限り読みにくく書くようにお願いしてある。
 無駄な処理満載の、本質がどこにあるのか非常に分かりにくい劣悪なコードだ。
「……でも、わたしたち以外に、CとGを通しているチームはいくつもあるよ? それに、実際にテストケースは間違ってないんだから、ジャッジを混乱させて、何になるの?」
 そう。タマキの言う通り、CとGをAcceptedしているチームが複数いる以上、これだけでは説得力に乏しい。
 そこで、フェイズ2だ。

「フェイズ2、始動」
 提出(サブミット)ボタンを連打して、CとGに似たようなコードを何回も送りつける。
 もちろんこれは、貴重な時間を使ってでも予め用意しておいたものだ。

 No - Wrong Answer.
 RE - Runtime Error.
 No - Wrong Answer.
 TLE - Time Limit Exceeded.
 RE - Runtime Error.
 OLE - Output Limit Exceeded.
 RE - Runtime Error.
 TLE - Time Limit Exceeded.
 No - Wrong Answer.
 No - Wrong Answer.
 OLE - Output Limit Exceeded.
 …….

 多種多様なエラーメッセージが、画面に並ぶ。
 よし、これで、嘘サブミット解析、終了だ。

 少しずつ条件を変えた多くのサブミットに対して、WA(Wrong Answer)RE(Runtime Error)TLE(Time Limit Exceeded)OLE(Output Limit Exceeded)のどの結果が返ってくるのかを見て、テストケースの入力データを解析する方法のことを、サブミット解析と呼ぶ。
 多くの場合、テストケースの中身を解析しただけではAcceptedを得ることはできず(結局は、判明したテストケースに対する正しい答えを自力で求めなければいけない)、やりすぎるとジャッジのサーバーに過剰な負荷をかける攻撃の一種と見なされて何らかの処分を受けることもあるため、サブミット解析は、あまり真っ当な手法だとは思われていない。

 とはいえ、それにも例外がある。
 その例外こそが、「テストケースの入力データに誤りがないか軽くチェックするのに使う」である。
 例えば、n≦50という制約のある問題で、もしnが51以上であればTLEになるコードを送信して様子を見る、といったように。
 ジャッジ側の助けになるサブミット解析というのも、存在するのだ。

 そして今回、あたしたちは、それを行った“ことにする”。

「Clar、送信っと」
 あたしはジャッジに、Clarification、つまり質問メッセージを送る(Clar自体は、ICPCのルールで正式に認められている行為だ)。
 内容は、こうだ。

 あたしたち、ノーネームの提出したCとGのプログラムが、何度やっても通りません。
 そこで簡単なサブミット解析を行ったところ、そちらの用意したテストケースに誤りが存在する可能性が高いことが判明しました。
 なので、改めてテストケースを詳しく調査し、もし誤りが発見されたら、正しい入力に差し替えてもらうことは可能でしょうか?

 と、まあ、こんな感じのメッセージを、普段使わないような丁寧な言葉で簡潔に書いて送っておいた(もちろんこれも、予め用意しておいたものだ)。

「テストケースを変えてもらうのが目的、なの? でも、これだけじゃ……」
 不安そうな目でこちらを見つめてくるタマキに言葉を返す前に、ジャッジからの返信メッセージが届いた。
 お。思っていたより反応が早いわね。優秀優秀。


 ――――申し訳ありませんが、その希望に答えることはできません。


「やっぱり……。そんな簡単に、ジャッジの人たちは動いてくれないよ……」
 がっかりして声を落とすタマキに、あたしは言う。
「いいのよ、これで」
「え?」
「そもそも、コンテストも残り30分を切ったこの段階で、今からテストケースの検証や、ましてや新しいテストケースを作って差し替えなんて、出来るわけないでしょ。だから、断られて当然」
 具体的に、どこがどう間違っているっていう指摘もないしね。
 だから、さっきのClarは、いわば軽いジャブのようなもの。
 本命は、次だ。

「行くわよ、最終(ファイナル)フェイズ」

 ――――そうですか、分かりました。残念です。
 ――――しかし、私たちには、どうしてもジャッジの用意したテストケースに間違いがあるように思えてならないのです。
 ――――そこで、せめて次のお願いを聞いていただけないでしょうか?

「サクヤちゃん、これって……」
「そ。これが本題。このお願いが通るかどうかが、この作戦の肝よ」
 最初のClarに対して返ってきた、素っ気ない否定の返事。
 だが、あれを書いたのは、まぎれもない人間だ。
 テストケースにミスがあることが発覚すれば、それはテストケースを作成したジャッジ側の責任問題。
 内心では、本当に自分たちの作ったテストケースが間違っているのではないかと、ヒヤヒヤしているに違いない。というか、そうでなくては困る。

「それなりに名が知られたあたしたちのチームが、あれだけしつこく間違ってます間違ってますって訴えてるんだもん。不安になって当然だわ」
 日本のジャッジの中には、あたしと個人的に知り合いな人も何人かいる。
 もちろんそれで直接的な便宜を図ってもらえるなんてことはありえないが、今は動揺させることだけが目的なのだから、コネクションがあるというその事実だけで十分だ。

 信用のある相手からの度重なる揺さぶりに、トドメのドア・イン・ザ・フェイス。
 これで落ちなければ、嘘だろう。

「サクヤ。返信」
 トウコに言われ、ジャッジから送られてきたメッセージを読む。


 ――――分かりました。それでは、今から5分後に、チーム【__________(ノーネーム)】が今まで提出したCとGの全てのコードに対して、リジャッジを行います。


「よしっ! 通った!」
 思わずガッツポーズ。これで、か細い道が繋がった。

 オペレーションRJ(ReJudge)、大成功だ。

 すでに提出されたコードに対して、もう一度ジャッジシステムを走らせる“リジャッジ”。
 普通は何か不具合が見つかって修正されたときなどに行われるそれを、あたしたちはジャッジに頼み込んで無理やり実行してもらった。

 テストケースを調査しろだの何だと言っていたあたしたちから、急に、ただリジャッジを行ってくれれば他には何もいらないという旨のメッセージが届く。
 何も条件を変えずにリジャッジを行ったところで、コンテストの進行に影響を及ぼすとは思えない。それに、リジャッジするだけなら、大した手間もかからない。
 そうであるからこそ、ジャッジは、厄介なクレーマーであるあたしたちを引き下がらせるために、この条件だけは呑んでくれると思ってたわ。

 そしてもちろん、あたしたちには、このリジャッジを利用するための策がある。

「さあ、タマキ。あんたの能力(スキル)、存分に活用させてもらうわよ」
「うん! 了解だよサクヤちゃん!」

 タマキは、いつも髪につけているダイス型のボンボン――というか、ボンボンのように見えるダイスを、2つ取り外して両手に握りしめる。
 目を閉じて、集中。
 そして、スキルの発動を、宣言する。


「<固定賽子(バウンドレス・ダイス)>」


 タマキの手から、ふわりと放られた2つのダイス。
 一切の回転運動なしに飛んでいった賽は、まるで定められた位置に吸い寄せられるように落下していき、机の上で、音を立てずに止まった。

 出た目は、1と1。

 タマキの能力(スキル)、<固定賽子(バウンドレス・ダイス)>は、「問題1問につき1つだけ、用意されたテストケースを、こちらで準備した入力データと入れ替えることができる」というものだ。
 このスキルとリジャッジさえあれば、あたしたちの策は実る。

「トウコ。CとGの追加ケース、準備できてるわね?」
「むろん」
 トウコの示したテキストファイルを、開いて確認する。

<inputC.txt>

20
A
B
C
D
E
F
G
H
I
J
K
L
M
AB
AC
BD
BE
CF
CG
GGG
Z Y X W V U T S R Q P O ZN NNN.
<inputG.txt>

4 15
***************
*4444444444444*
*44************
***************

 うん、これなら大丈夫。

入れ替え(スワップ)完了だよ、サクヤちゃん!」
「よし。あとは、リジャッジの結果を待つだけね」

 C問題とG問題は、いわゆる“探索”と呼ばれるジャンルの問題だ。
 探索問題の最大の特徴は、計算量のオーダーはおろか、いったいどのくらいの時間で計算が終了するのか、大雑把にでも見積もるのが非常に難しいことにある。

 タマキとあたしは、まず、CとGについて、ジャッジの用意したテストケースくらいなら全て通るであろうという程度のプログラムを作成した(これは自然な枝狩りをいくつか入れたらすぐに達成できた。TLEにならないことの確認には、もちろん“食道デバッグ”を使った)。
 そして、そのプログラムをトウコに読ませ、2人の書いたプログラムがTLE(またはMLE(Memory Limit Exceeded))するような撃墜ケースを作ってもらった。
 最後に、タマキとあたしが、トウコの作った撃墜ケースを含めて、どんな入力が来てもTLE・MLEしないようにプログラムを改良する。
 ジャッジに提出してわざとWrong Answerを連発したプログラムは、この改良後のプログラムに、特定のテストケースにだけ間違った解を返すようなコードを書き加えたものだ。

 そして、その“特定のテストケース”は、タマキの<固定賽子(バウンドレス・ダイス)>で取り除いた(固定賽子は、自分で用意したテストケースを、上から何番目のテストケースと入れ替えるか選択することができる)。
 もちろん、あたしたちが仕込んだ意図的なWAは、代わりに追加されたトウコ謹製のテストケースには反応しないようになっている。

 すると、リジャッジの結果はどうなるか。

「サクヤちゃん! リジャッジ開始だって!」
 先ほどの返信メッセージから、ちょうど5分が過ぎた。
 リジャッジ自体は一瞬で終わり、最初の方で投げた大量のWrong Answerが、一斉に評価を反転させる。

 Yes - Accepted.
 Yes - Accepted.
 Yes - Accepted.
 Yes - Accepted.
 Yes - Accepted.
 Yes - Accepted.

 無論、同じ問題で何度もAcceptedをもらったところで、完数が重複したりはしない。
 とはいえ、これで+2完で、合計8完。当然、CとGのペナルティタイムの上乗せは全て無効だ。

 さらに、この+2完には、ただの2完だけに留まらない、大きな意味がある。


チェックメイトよ。緋笠カズミ」


 ――――たった今、リジャッジが行われたことで、今までWrong Answerだった私たちのコードが、一斉にAcceptedになりました。
 ――――どういうことかは分かりませんが、私たちがこれまで主張してきた不具合が、解消されたということでしょうか。
 ――――どちらにしても、こうなった以上、公平を期すために、全チームのC問題とG問題のソースコードを、一斉にリジャッジにかけるべきではないでしょうか?



4:43経過 【玉兎(たまうさぎ)】 ABCDEFGIJ 9/10完


 風船が割れる音、というものを、緋笠カズミは初めて耳にした。


 無論、ただの風船が割れる音なら、何度も聞いたことがある。
 だが、ここはICPCのコンテスト会場で、今はコンテストが行われている真っ最中だ。
 そこで、風船が割れるということは。
 すなわち、完数が減った、ということに他ならない。


「何が、起きた……!?」
 緋笠カズミの端正な顔が、驚愕に染まる。
 突然、会場中に大きな音が連鎖的に鳴り響いたかと思えば、それまで上がっていた黄色の風船(C問題)と水色の風船(G問題)が、立て続けにいくつも消滅した。

 風船が、割れた。
 その事実を認識するまでに、カズミは、たっぷり数十秒もの時間を要した。

 そして、ふと顔を上げ、順位表を見やると。

「馬鹿な……!」


 現在の順位:
 1位 【__________】 ABCDEFGJ 8完 ペナルティ+1190
 2位 【玉兎】 ABDEFIJ 7完 ペナルティ+861
 3位 【ブレインネクサス】 ABFHI 5完 ペナルティ+495


 今の今まで9完だったはずの【玉兎】のスコアが7完にまで転落し、
 ついさっきまで6完だったはずの【__________】のスコアが、8完になっている。
 いったい何が起こったのか、まるで理解できない。

 反射的に、ノーネームの机の方に目を向ける。
 すると、秋葉サクヤが、勝ち誇ったような顔でこちらを見返してきた。

 自然、視線が交錯する。
 そこがコンテスト会場である限り、優れたプログラマー同士の会話には、必ずしも言語によるコミュニケーションが必要とされない。視線に込めた強い意志。それだけがあれば十分だ。
 濃縮された時間の中で、2人の競技プログラマーが、目と目だけで会話を交わす。

 ――おや。そこの赤白(ターゲット)コーダーさんは、何が起きたかまるで分かんないって顔してるみたいね。あたしが教えてあげましょうか?
 ――く……。済まないが、ご教授願おうか。
 ――あら、簡単なことよ。ジャッジからの公式アナウンス、見てないの?

 それを聞いて、カズミは自分のパソコンのディスプレイに視線を戻す。
 風船が割れたことで呆然として気づかなかったが、確かにジャッジから全チームへの通達メッセージが、1件届いていた。
 そこには、C問題とG問題について、全チームの提出コードのリジャッジが行われ、その結果に応じて順位が再計算された、とある。

 ――……なるほど、そういうことか。
 ――何? どういうことか分かったの? 言ってみなさいな。あたしが採点してあげるから。
 ――君達は、何かしらの能力(スキル)を使って、CとGのテストデータに修正を加えた。そして、何らかの方法で、リジャッジが行われるよう審判団(ジャッジ)を誘導した。違うかい?
 ――何らかのが多すぎるけど、ま、おおむね会ってるわ。60点てとこね。ちなみに、テストデータを入れ替えたのは、あんたにはまだ見せたことのない、タマキのスキルよ。本格推理(ミステリ)じゃないんだから、まさかアンフェアだなんて言わないわよね?
 ――無論だとも。
 ――あんたに速度で勝てないんなら、完数で勝てばいい。そのためには、緋笠カズミ、あんたの完数を減らすのが一番手っ取り早い。簡単な理屈でしょ?
 ――まさか、ICPCで撃墜なんて真似をしてくるとはね。その発想力には、素直に感服するよ。自分のコードがChallenge Succeededされるなんて、TopCoderでも久しく味わったことのない経験だからね。
 ――ちっ、これだから赤白は。……ま、さっき、あんたが本気で驚いた顔を見れたからよしとするわ。写真に撮れなかったのが残念だけど。
 ――……それにしても、一つ気になることがある。
 ――何? まあおおよそ予想はついてるけど、訊いてごらんなさい? 今のあたしは機嫌がいいから、大抵のことは教えてあげるわよ。
 ――テストケースを修正し、リジャッジを誘導したこと。そこまではいい。……だが、君達は、なぜ私のコードを撃墜できるという確信を持てた? それとも、そんな確証はなく、とにかく賭けに出てただ偶然勝っただけだとでも言うのかい?
 ――確証? もちろんあったわよ。運否天賦も嫌いじゃないけど、勝つべくして勝つ方が、あたしの好みなの。覚えてる? あたしが主催した、プログラミングコンテスト
 ――UTPC、か。
 ――そ。誰かさんが圧倒的大差で1位になった挙句、あたしに向かって「君と競い合えなかったのは残念だな。また今度、コンテストの参加者という立場同士で闘いたいね」なんて腐れた台詞を吐いた輩がいた、あのコンテストよ。
 ――……なかなか手厳しいね。
 ――あたしがあれを主催した目的は、緋笠カズミ、あんたについて、いくつかの事柄を確認することだった。具体的には、コーディングの癖と、それから、<解法解放(ヘウレカ)>の正確な特性。
 ――まさか……!
 ――そ。そのまさか。あんたの<解法解放>は、与えられた問題に対する正しい解法を与えてくれる能力(スキル)じゃない。<解法解放>がもたらしてくれるのは、与えられた問題と、用意されたテストデータに対して、そのテストデータを通すのに十分なだけのできる限り簡潔な解法。あたしは、UTPCの問題の中に、わざと弱いテストデータを紛れ込ませて実験した。案の定、あんたの提出したコード、コンテスト後に改めて最大ケースを投げてみたら、撃墜できたわよ。……あとはまあ、ダンジョンを探索する問題が出たときに、xのループよりもyのループの方を外側に書くとか、そういう細かい癖をちょこちょことね。
 ――……確かに、C問題とG問題は、私のコードでは、最悪のケースに関しては解ききれないという自覚はあった。だが、一度Acceptedをもらえば、たとえ嘘解法だろうと問題ないのが競技プログラミングの世界だ。だから、
 ――ああ、まあ、基本的にはあんたの言う通りね。現に、OB/OGの会主催のコンテストなんかでは、Wrong AnswerがAcceptedになることはあれど、逆はない、ってのが慣例だしね。でも、ICPCの公式ルールには、そんなこと、ひとっことも書かれてないのよ。むしろあたしは、今回の処置の方がよっぽど公平に思えるわね。ほら。テストなんかでたまに、「出題ミスがあったので、この問題は全員正解にします」ってのあるじゃない? あれだって結局、その問題に時間を注ぎ込んでしまった生徒が不利になるのは変わらないじゃない。だからね、ジャッジのミスが判明したなら、素直にAcceptedだろうがWrong Answerにしちゃっていいわけよ。分かる?
 ――はは。いっそ清々しいほどの詭弁だな。テストデータを改竄した張本人が、何を言うかと思えば。
 ――なんだ、ちゃんと分かってるじゃない。それで、どうする? ジャッジにあたしたちを訴えでもする?
 ――いや、止めておくよ。ICPCのルールに、悪意あるクラッキングを禁止する項目はあれど、能力(スキル)によるハッキングを禁止する項目はない。そもそも、競技プログラマーである以上、自らに宿ったスキルは全力で活かしてこその、真剣勝負だからね。
 ――あら。珍しくあんたと意見が一致したわね。明日は雪でも降るんじゃないかしら。
 ――はは。とにかく、今日は負けを認めよう。私の完敗だ。賭けのルールに則って、昨年奪ったチーム名は、君達に返還しよう。
 ――よろしい。この期におよんで、見苦しく足掻かないところだけは評価してあげてもいいわ。
 ――感謝するよ。それでは、敗者は去るとしよう。ICPC世界大会、頑張ってくれたまえ。
 ――ふん。言われなくてもね。……あ、そうそう。たった今、タマキが組んだIのコードを、トウコが食道デバッグし終えたらしいわ。それじゃ、また縁があったら会いましょ。

 秋葉サクヤが目をそらし、視線での会話が途切れる。
 その間、わずか2秒。

 直後、ノーネームの机の上に、I問題を解いた証である黄緑色の風船が浮かび上がる。
 これでノーネームは、ABCDEFGIJの9完。
 一方で、玉兎の完数は、サクヤの策略によって7完にまで落ち込んだ。


「ああ……。2完差というのは、ここまで絶望的な違いだったのだな」


 緋笠カズミは、そう、ぽつりと呟いた。



4:46経過 【世界一(せかいいち)】 0/10完

「……驚きました。まさか本当に、あの緋笠カズミが、ノーネームに敗れ去るなんて」
 里山(さとやま)アイチは、心底驚嘆したという風に言う。

 風船が割れた瞬間、何が起こったのか。ノーネームが何を考え、何を実行に移したのか。
 それらは全て、絵空(えそら)トオルから説明を受けてはいたものの、それでも驚きは止まなかった。

 ノーネームが逆転の刃を振り下ろすタイミングも、実に絶妙だった。
 これが30分も40分も時間が残っているときの出来事であったなら、緋笠カズミほどの腕の持ち主なら、風船を割られた所から巻き返しを図ることも余裕でできただろう。
 しかしもう、残り時間はわずか十数分だ。
 改めて、ノーネームが入れ替えたテストケースに対応するようにCまたはGのプログラムを書き変えようにも、カズミにしてみれば、加えられたテストケースがどういった種類のコーナーケースなのか確かめている時間はない。
 そうなれば、あらゆる入力に対応できる、きちんとしたプログラムを組まなければいけなくなり、とても今から2完を稼ぐには時間が足りない。

 <二重能力(ミメーシス)>でタマキの<固定賽子(バウンドレス・ダイス)>をコピーして、追加されたテストケースを無害なケースと入れ替えようにも、それが入力の何番目にあるのか分からないのでは実行に移せない。
 カズミも同じようにリジャッジを請求して通ったとしても、ノーネームのコードを撃墜できるとは到底思えない。可能性があるとしたら、ノーネームがDを単純なダイクストラ解法で通していた場合だが、彼女らがあらかじめこの撃墜作戦を見越していたとすれば、そんなわざわざ隙を作るような真似はしないだろう。

 と、そこまで考えて、ふと、以前トオルが呟いた言葉を思い出す。

 ――あなたは、ノーネームが優勝できる可能性は、どのくらいあると考えているんですか?
 ――そうねぇ。五分五分、ってところかしらねぇ?

 アイチにしてみれば、ノーネームは勝つべくして勝ったように見えるが、それでも勝率は五分五分だったらしい(絵空トオルの、競技プログラマーを見る目は実に正確なのだ)。
 確率50%の賭けに勝った挑戦者に、素直に称賛の拍手を送りたいと思う。

「あら? アイチちゃん、その顔は、何か大事なことを勘違いしているわねぇ?」
「……? 勘違い、ですか?」
「もしかして、もうコンテストは終わった、なんて考えてるんじゃないかしら?」
「……ええ。だって、もう事実上の決着はついたでしょう。ブレインネクサスは緋笠カズミの<二重能力(ミメーシス)>に敗れ、その緋笠カズミはノーネームの策略に負けた。もうこれ以上、逆転の余地は残っていないと思いますが」
 そう言ってから、気づく。
「まさか、トオルさん。今からコンテストに参加する気なんですか?」

 赤白(ターゲット)を超えた、色無し(No Rated)
 絵空トオルは、多くの競技プログラマーから、畏怖と敬意を込めて、そう呼ばれている。
 全世界の競技プログラマーの頂点に立つ彼女に色が無い理由は、既存のレーティングシステムでは彼女の実力を測れないからだとか、そもそもTopCoderを管理しているのが絵空トオル本人であるからだとか、様々な噂が絶えない(トオル本人はそのあたりの事情について語りたがらないため、アイチにも真相は謎)。

 そんな彼女であれば、たとえ残り時間があと10分を下回りそうな今この瞬間からコンテストに参戦したとしても、ぶっちぎりで1位を取れるだろう。
 彼女の能力(スキル)、<全完(パーフェクト)>の前では、緋笠カズミも、ノーネームも、何もかもが無力なのだから。

「そんなことはしないわよぉ。だって、お姉さんが1位になっても、面白くも何ともないもの」
 自分が1位になれることは一切否定せずに、とろけるような声で言う。
「お姉さん言ったでしょ? サクヤちゃんたちノーネームが優勝できる確率は、五分五分だ、って」
「? ですから、その五分五分の賭けにノーネームが勝ったから、今」
「違うわよぉ。残りの五分の方は、カズミちゃんじゃなくてぇ」
 トオルが言い終わる前に、アイチは、順位表に現れた、とある変化に気づく。

 先ほどの風船が割れた爆音の嵐に比べれば、実に静かな、ある変化。
 しかし、その一見さりげない変化は、コンテストの流れを、激変させる。
 まるで、今までの全ては、しょせん予定調和だったとでも言うかのように。

「これは……、一体……!」
「だからぁ」
 当然、その変化も予想していたとばかりに、絵空トオルは口を開く。



「サクヤちゃんがカズミちゃんにやったのと同じことを、今度はノーネームがやられちゃったのよぉ」





(No.3/3につづく)