2011-12-23
__________の ＩＣＰＣアジア地区予選２０１１参戦記 No.2/3
１：５４経過 【__________ 】 ＡＢＦ ３/１０完
「ちっ。
ぐしゃぐしゃと髪をかき回す。
くそっ。カズミの奴は、もうＡＢＣＦＧの５完だってのに……。
とはいえ、ここで焦っても仕方ない。
絶対にバグを出さないなんて、一部の人外を除けば普通のプログラマーにはまず不可能。
肝心なのは、バグを出してしまったときに、いかに速やかに対処するかだ。
このままパソコンを使ってデバッグする手もあるが、サンプルは通っていてＷＡの原因が推定できていない以上、ここはいったん手を引くのが最善だろう。
それに、うちのチームには、こんなときのための秘密兵器がいるわけだしね。
「トウコ。いつものやつ、任せたわよ」
「いぇっさー」
バグの入ったＤ問題のソースコードを印刷して、トウコに渡す。
普通なら、この紙をじっと睨んで隠れたバグを探すのかと思うでしょうけど、そうじゃない。
トウコは、無表情な瞳で、じっとプログラムを見つめていたかと思うと、唐突に、
ぴりぴり、と。
紙の上端を細長く切り取るように指で破り、そして、
ぱくり、と。
食べた。
……うん。何を言っているのかわからねーと思うから、今から説明する。
トウコは、ソースコードが印刷された紙を、（比喩ではなく）「食べる」ことで、バグの有無や種類を判別することができる。
ちなみにこれは、強豪プログラマーの多くが持っている“
ぶっちゃけあたしも、こいつがこんなことをできる理由も原理もまるで理解しちゃいないんだけど、とにかくトウコには、そういう得体の知らない“力”がある（本人に訊いても、「……気合と経験？」などと首を傾げてやがったので、たぶん自分でも分かってない）。
無論、原理なんて分からずとも、できる以上は存分に利用させてもらう。
あたしたちがリスク覚悟で完全分業体制を実行に移せているのは、もしバグを出したとしてもトウコがいるという安心感によるところが大きい。
「んぐ。のどごし爽快。バグはない」
紙の上に印刷されたソースコードを、数行ずつまとめて手で破ってから、むしゃむしゃ食べる。
これが、バグのある箇所だと、喉に詰まる感じがするらしい。
また、「のどごし」の違いで、そのバグが
この説明も光景も何もかもシュールなのだが、もう慣れた。
「もぐもぐ。うまい。バグなし」
本人いわく、コードの食べ心地の見極めは繊細な作業らしいので、１つのコードをデバッグするのには、コードの長さにもよるが、普通１０分から数十分と、無視できない時間がかかる。
これをやっている間、トウコは問題を解けなくなるわけで、あまり乱用できる手ではないものの、それでも有限の時間でバグが取れることが保証されているのは大きい。
ちなみにあたしたちは、この技のことを“食道デバッグ”と呼んでいる。
そしたらいつの間にか、トウコは“
本人はこの名を悪く思っていないらしく、食道デバッグの様子を見た誰かによってつけられた異名だと主張してはいるけれど、おそらくはいつ見ても何か食ってるトウコに呆れはててつけた名前なんだろう。間違いない。
閑話休題。
Ｄのデバッグはトウコに任せておけばいいとして、次は。
「タマキ。今すぐに解き始められる問題、何かある？」
残念ながら、あたしには今すぐパソコンを使ってできることは何もない。
代わりに、今まで待機していたタマキに、現状を訊ねる。
「Ｉ問題なら、たぶん時間があれば解けるとは思うけど……」
Ｉか。たしかブレインネクサスが序盤に速攻で通してたわね。
幾何問題か。確かにタマキが得意なジャンルではある。
だけど。
「これ、おそらく実装かなり面倒臭いわよ。まだ５問目だし、他に何か……」
ないの？ と口を出そうとしたところで、タマキに割り込まれる。
「うん、それでねサクヤちゃん。さっき気づいたんだけど、このＥ問題なんて面白そうじゃない？」
「Ｅ……？」
順位表を見上げる。Ｅ問題は、まだ誰一人として通していない。
「どんな問題なのよ……ってこれ、まさか！」
三角格子の上を、正二十面体が転がっている図。
１つ１つの面にユニークな番号が振られた、正二十面体の展開図。
そして、問題文の端々から察するに、これは……。
「たぶん、（０，０）に０番の面が接している状態からスタートして、正二十面体を転がしていって、ゴールの（Ｘ，Ｙ）にｎ番の面が接している状態にするまでの最短手数を求めなさい、って問題だと思う」
「超っ絶に面倒臭いじゃないの……本質とは全然関係のないところで……」
幅優先探索を、するだけ。
でも、そのStraightforwardな段階に達するまでに、無駄に大きな壁がある。
「おそらく、この図を切り取って、実際に組み立ててみましょうって問題よね。これはこれで、相当面倒くさい……って、あ、そういえば、あんた」
ふと気づく。
タマキは、コンテストの度に、お守りとして趣味の色々な形をしたダイスを持ち込んでいたことに。
「そうか……。正二十面体のブランクダイスを使えば……！」
工作の手間が、大幅に省ける。
「よしタマキ！ ＧＯ！」
「了解だよっ！ サクヤちゃん！」
嬉々として、空いたパソコンの前に座るタマキ。
タマキに任せておけば、この問題は解けたも同然だろう。
……って、あれ？
「ねえタマキ。でも結局、正二十面体の面の推移関係を求める段階では、パソコン使わないんじゃ――――」
まずは、紙の上で、これを打ち込めばいいって段階まで固めてから――――。
そう言おうとしたけれど、その言葉は途中で呑み込まざるを得なかった。
「５，１，４！ ６，２，０！ ７，３，１！ ８，４，２！ ９，０，３！ ０，１０，１１！ １，１１，１２！ ２，１２，１３！ ３，１３，１４！ ４，１４，１０！ ５，９，１５！ ６，５，１６！ ７，６，１７！ ８，７，１８！ ９，８，１９！ １０，１９，１６！ １１，１５，１７！ １２，１６，１８！ １３，１７，１９！ １４，１８，１５！ できたっ！」
またたく間に、
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}, };
様々なダイスが詰め込まれたタッパーは、結局一度も開かれることはなかった。
「タマキ……あんたこれ、全部今の一瞬で、脳内で？」
「ん、どうしたのサクヤちゃん？ だってここに展開図と面の番号が書いてあるから、これを組み立てた通りに打ち込むだけだよ？」
当たり前のことをやっただけなのに、と不思議そうに首を傾げる。
そんな愛くるしい表情のタマキに向かって、あたしは。
「タマキ偉いぞよくやったっっ！！」
「わ、わ、サクヤちゃん。どうしたの、急にっ！」
顔を赤らめるタマキを、思いっきり抱きしめる。
もう……っ。最高だよ、あんた！
１０分後。
「よーしっ！ 幅優先探索終わりっ！ サブミット！」
ジャッジにＥのコードが転送され、即座に結果が返ってくる。
Yes - Accepted.
グレーの風船が打ち上がり、４完。
そして、同時に。
「んぐぅ。サクヤ、この行、喉に詰まって食べにくい」
トウコが指さす、半分くらい食べかけの行に書かれている文字列は。
vector<pair<int, int> > adj[3010];
「なるほどそこかぁっ！ トウコ、サンキュ！」
道の上限は３０００本でも、街の上限は６０００個！
そりゃあWrong Answerするわけだよ！
３を６に書き換えて、サブミット。
Yes - Accepted.
「よっしゃあっ！ これで一気に５完！」
経過時間は２：１５。
ちょっと手間取りはしたけど、悪くないタイムだ。
「ねえサクヤちゃん。このＤのソースコードだけど、なんでわざわざ、コード量の多いこっちの解法で書いたの？」
「ん。ああ、そのこと？ まあ、色々思うところがあってね」
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を出力せよ。
Ｎ≦３０００に対してＭ≦３００であることから察するに、おそらくこの問題の作為解は、「ガソリンスタンドの存在する街を始点としたダイクストラ法を計Ｍ回行い、最後にガソリンスタンドのある街だけをノードとしたグラフ上でスタートからゴールへの最短路問題を解く（ちなみにここでワーシャルフロイド法を利用できる）」だろう。
要するに、ガソリンという概念がなかった場合の問題に帰着して考えるわけだ。
しかし、ガソリンの残量の取りうる値が高々２００１通りの離散値しかないことを利用すると、（車が今いる街，ガソリンの残量）を状態に持ったよくあるダイクストラ一発で解くこともできる（この際の状態数は、約６０００×２０００に見えるが、スタートから辿りつける街は高々３０００個しかないので、実は約３０００×２０００）。
前者の解法は、まず制限時間を超過する危険性はないだろうけど、後者の解法は、もしかするとＴＬＥするかもしれない微妙なラインだ。
とはいえ、日本の
だとすれば、実装が楽で、早く書ける後者の解法を選ぶべきではなかったのか。
タマキは、こう言いたいのだろう。
もちろんあたしも、そんなことは分かっている。
それでも前者の解法を選んだ理由は、用意されたテストケースが万が一強かった場合を恐れた、というのも無くはないんだけれど――――。
「＜
「？？？？」
タマキの頭の中に、疑問符がいっぱい浮かんでいるだろうことが、目で見ても分かる。
ごめんね。今は説明できないの。あんた、人に物事を隠すのとか苦手そうだし。
「詳しくは後で教えてあげるわ。さ、２人とも、これからやることを話すわよ」
ＤのデバッグとＥのコーディングが行われている間に、あたしは今後の方針を決めていた。
タマキとトウコに出す指示も、できる限り固めてある。
チームの力を最大限に引き出す戦略を練るのが、リーダーの役目だ。
みんな、お願い。あたしについてきて。
必ず、カズミの野郎をぶっ倒してみせるから。
２：２１経過 【玉兎 】 ＡＢＣＤＦＧ ６/１０完
「ノーネームがＥ問題を１４分で提出、か。ふふ。あそこのチームには渡部タマキが居るからね」
相手の動きは手に取るように分かるとばかりに、緋笠カズミはくつくつと笑う。
「他のチームが必死に展開図を組み立てている中で、唯一正二十面ダイスをコンテスト会場に持ち込んでいた奇特な彼女らはといえば、そのダイスを取り出して眺めることすらしなかった、か。……やはり、君達のチームは面白いな、秋葉サクヤ」
横目でノーネームの机を観察しながら、告げる。
「見事なファインプレーだった。素直に拍手を送ろう。……けど、残念だな」
言葉とは裏腹に、不敵な笑みを浮かべながら。
「その程度の奇跡では、決して私には届かない」
Yes - Accepted.
玉兎の机に、グレーの風船が上がる。
ＡＢＣＤＥＦＧ ７/１０完。
Ｅ問題を解くのに要した時間は、１３分。
＜
タマキがあれほどの快挙を成し遂げてもなお、カズミには及ばない。
３位の３完チームに２完差をつけて圧倒しているノーネームにすら、さらに２完差をつけて独走する、チーム【玉兎】。
２つの
「さあ、ラストスパートだ。終盤戦の開始と行こうじゃないか」
３：５２経過 【__________ 】 ＡＢＤＥＦ ５/１０完
「よし。Ｊ問題、Accepted」
紫の風船が打ち上がる。これでようやく６完だ。
Ｊ問題は、アジア地区予選には珍しい、高度なアルゴリズムを考えさせる良問だった。
とはいえ、「同じ高さにある街は高々１０個です」という露骨な条件があったおかげで、１０を２の肩に乗せるという発想に至るのは比較的簡単だった。
すでに残り８０分を割っている状態で６完というこの現状だけを見れば、あまり芳しくない状況である。
でも、そうじゃない。
今、ノーネームの水面下では、いくつもの作業が並行して動いている。
「タマキ、トウコ。完全分業体制は終わり。今からあたしの言う指示に、従って」
５完した直後、あたしは２人に向かってそう言った。
このまま真っ当に闘っていても、カズミには勝てない。
だからこそ、策を練る。
完数の期待値を下げてでも、優勝する確率を最大化するために動く。
カズミが玉兎を名乗るなら、あたしたちは金烏になって、あんたの積み上げてきたものを焼き尽くしてやる。
「んぐ。デバッグ完了。２つのコードのバグは、あらかじめ全て取りきった」
「サクヤちゃーん！ Ｉの実装、紙の上で詰めておいたよー」
「サンキュ２人とも。次、トウコは手動でさっき言ったテストケースの作成、タマキはそのままＩのコーディングに入って」
「いぇあー」「分かったよっ！」
休む間もなく、次の指示を飛ばす。
もう残り時間も少ない。間に合うかどうかギリギリだから、死ぬ気で働いてもらうしかない。
幸い、今のところ、２人はあたしの言いつけたタスクを、大きなバグを出すこともなく的確にこなしてくれている。こちらは、このまま行けばおそらく問題ないだろう。
不安が残るとすれば、それはあたしだ。
なにせ、こんなこと、今までどのコンテストでだって経験がない。
成功するかどうかは賭けだと言っていい。失敗すれば、もう後がない。
それでも必死に知恵を絞って、少しでも成功確率を上げるために、想像する。予測しきる。
あたしたちの思惑、カズミの思惑。
そして、
そして、３０分後。
「さ……。行くわよ」
少し遅れて、もう１回。
これで、ＣとＧのコードが、ジャッジのもとへと送られていったことになる。
結果は。
No - Wrong Answer.
No - Wrong Answer.
……ふう。
予想通り、ＷＡをもらう。これで、どちらの問題も、通算３回目のWrong Answerだ。
「そろそろいいかしらね。オペレーションＲＪ、フェイズ２に以降するわ」
呟いて、汗をぬぐう。
それにしても、今回はやけに故意のＷＡに縁があるというか何というか。
とはいえ、今回の作戦は、最強最速の双子を相手にしたときとはわけが違う。
相手の反応を伺うことができない中で、それでも繊細な進行が要求される。
「……ねえ。サクヤちゃん。わたしたち、さっきから一体何をやってるの？」
タマキが、分からないなりにもこの場に漂う緊張感のようなものは伝わっているらしく、おずおずと訊ねてくる。
万が一カズミの奴にでも察せられたら厄介だから、隠し事がすぐに表情に出そうなタマキには黙っていたんだけど、まあ、少しずつ説明していきましょうか。
「さっきから、１０分くらいの間隔を開けて、何度もＣとＧのコードを送信しているでしょ？ あれは、バレないように少しずつ内容を書き変えているとはいえ、基本的にやっていることは全部同じ。あたしたちが送っているのは、特定番目のテストケースだけ、わざと間違った答えを返すプログラム」
ＷＡになって当然。むしろ、ＷＡになってくれなければ困る。
ちなみに、送ったソースコードが確実に意図した挙動をしてくれることは、トウコの“食道デバッグ”で念入りに確認済みだ。
「？ そんなことして、何かいいことあるの？」
「直接的にはないわ。けど、
意外と知られていないことだが、ＩＣＰＣのジャッジは、全自動で行われているわけではない。
参加者からサブミットされたコードをコンパイル、実行するところまでは自動的に進むが、そうして出た結果（Accepted、Wrong Answer、Time Limit Exceededなど）が順位表に反映されるためには、必ず１人以上のジャッジが目視で承認をしてやる必要があるのだ。
悪意のあるクラッキングなんかを防ぐための処置なんでしょうけど、今回はそれを利用させてもらう。
ジャッジといえど、あくまでも人間だ。そこには感情があるし、心が揺れ動きもする。
１位の玉兎には大差をつけられているとはいえ、２位のあたしたちノーネームが、何度も何度もＣとＧを提出し、その度にたった１つのテストケースでだけWrong Answerを出しているとなれば、動揺しないわけがない。
すなわち、自分たちの作成したテストケースが、間違っているのではないか、と。
「よっぽど特殊なコーナーケースでもない限り、たった１つのケースだけ落ち続けるなんてこと、あんまり無いからね。まさか、あたしたちが意図的に間違った回答を出力するプログラムを書いているなんて、考えもしない」
万が一ジャッジに提出したソースコードを読まれても大丈夫なように、タマキとトウコには、ＣとＧのコードはできる限り読みにくく書くようにお願いしてある。
無駄な処理満載の、本質がどこにあるのか非常に分かりにくい劣悪なコードだ。
「……でも、わたしたち以外に、ＣとＧを通しているチームはいくつもあるよ？ それに、実際にテストケースは間違ってないんだから、ジャッジを混乱させて、何になるの？」
そう。タマキの言う通り、ＣとＧをAcceptedしているチームが複数いる以上、これだけでは説得力に乏しい。
そこで、フェイズ２だ。
「フェイズ２、始動」
もちろんこれは、貴重な時間を使ってでも予め用意しておいたものだ。
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.
……．
多種多様なエラーメッセージが、画面に並ぶ。
よし、これで、嘘サブミット解析、終了だ。
少しずつ条件を変えた多くのサブミットに対して、
多くの場合、テストケースの中身を解析しただけではAcceptedを得ることはできず（結局は、判明したテストケースに対する正しい答えを自力で求めなければいけない）、やりすぎるとジャッジのサーバーに過剰な負荷をかける攻撃の一種と見なされて何らかの処分を受けることもあるため、サブミット解析は、あまり真っ当な手法だとは思われていない。
とはいえ、それにも例外がある。
その例外こそが、「テストケースの入力データに誤りがないか軽くチェックするのに使う」である。
例えば、ｎ≦５０という制約のある問題で、もしｎが５１以上であればＴＬＥになるコードを送信して様子を見る、といったように。
ジャッジ側の助けになるサブミット解析というのも、存在するのだ。
そして今回、あたしたちは、それを行った“ことにする”。
「Clar、送信っと」
あたしはジャッジに、Clarification、つまり質問メッセージを送る（Clar自体は、ＩＣＰＣのルールで正式に認められている行為だ）。
内容は、こうだ。
あたしたち、ノーネームの提出したＣとＧのプログラムが、何度やっても通りません。
そこで簡単なサブミット解析を行ったところ、そちらの用意したテストケースに誤りが存在する可能性が高いことが判明しました。
なので、改めてテストケースを詳しく調査し、もし誤りが発見されたら、正しい入力に差し替えてもらうことは可能でしょうか？
と、まあ、こんな感じのメッセージを、普段使わないような丁寧な言葉で簡潔に書いて送っておいた（もちろんこれも、予め用意しておいたものだ）。
「テストケースを変えてもらうのが目的、なの？ でも、これだけじゃ……」
不安そうな目でこちらを見つめてくるタマキに言葉を返す前に、ジャッジからの返信メッセージが届いた。
お。思っていたより反応が早いわね。優秀優秀。
――――申し訳ありませんが、その希望に答えることはできません。
「やっぱり……。そんな簡単に、ジャッジの人たちは動いてくれないよ……」
がっかりして声を落とすタマキに、あたしは言う。
「いいのよ、これで」
「え？」
「そもそも、コンテストも残り３０分を切ったこの段階で、今からテストケースの検証や、ましてや新しいテストケースを作って差し替えなんて、出来るわけないでしょ。だから、断られて当然」
具体的に、どこがどう間違っているっていう指摘もないしね。
だから、さっきのClarは、いわば軽いジャブのようなもの。
本命は、次だ。
「行くわよ、
――――そうですか、分かりました。残念です。
――――しかし、私たちには、どうしてもジャッジの用意したテストケースに間違いがあるように思えてならないのです。
――――そこで、せめて次のお願いを聞いていただけないでしょうか？
「サクヤちゃん、これって……」
「そ。これが本題。このお願いが通るかどうかが、この作戦の肝よ」
最初のClarに対して返ってきた、素っ気ない否定の返事。
だが、あれを書いたのは、まぎれもない人間だ。
テストケースにミスがあることが発覚すれば、それはテストケースを作成したジャッジ側の責任問題。
内心では、本当に自分たちの作ったテストケースが間違っているのではないかと、ヒヤヒヤしているに違いない。というか、そうでなくては困る。
「それなりに名が知られたあたしたちのチームが、あれだけしつこく間違ってます間違ってますって訴えてるんだもん。不安になって当然だわ」
日本のジャッジの中には、あたしと個人的に知り合いな人も何人かいる。
もちろんそれで直接的な便宜を図ってもらえるなんてことはありえないが、今は動揺させることだけが目的なのだから、コネクションがあるというその事実だけで十分だ。
信用のある相手からの度重なる揺さぶりに、トドメのドア・イン・ザ・フェイス。
これで落ちなければ、嘘だろう。
「サクヤ。返信」
トウコに言われ、ジャッジから送られてきたメッセージを読む。
――――分かりました。それでは、今から５分後に、チーム【
「よしっ！ 通った！」
思わずガッツポーズ。これで、か細い道が繋がった。
オペレーション
すでに提出されたコードに対して、もう一度ジャッジシステムを走らせる“リジャッジ”。
普通は何か不具合が見つかって修正されたときなどに行われるそれを、あたしたちはジャッジに頼み込んで無理やり実行してもらった。
テストケースを調査しろだの何だと言っていたあたしたちから、急に、ただリジャッジを行ってくれれば他には何もいらないという旨のメッセージが届く。
何も条件を変えずにリジャッジを行ったところで、コンテストの進行に影響を及ぼすとは思えない。それに、リジャッジするだけなら、大した手間もかからない。
そうであるからこそ、ジャッジは、厄介なクレーマーであるあたしたちを引き下がらせるために、この条件だけは呑んでくれると思ってたわ。
そしてもちろん、あたしたちには、このリジャッジを利用するための策がある。
「さあ、タマキ。あんたの
「うん！ 了解だよサクヤちゃん！」
タマキは、いつも髪につけているダイス型のボンボン――というか、ボンボンのように見えるダイスを、２つ取り外して両手に握りしめる。
目を閉じて、集中。
そして、スキルの発動を、宣言する。
「＜
タマキの手から、ふわりと放られた２つのダイス。
一切の回転運動なしに飛んでいった賽は、まるで定められた位置に吸い寄せられるように落下していき、机の上で、音を立てずに止まった。
出た目は、１と１。
タマキの
このスキルとリジャッジさえあれば、あたしたちの策は実る。
「トウコ。ＣとＧの追加ケース、準備できてるわね？」
「むろん」
トウコの示したテキストファイルを、開いて確認する。
<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************ ***************
うん、これなら大丈夫。
「
「よし。あとは、リジャッジの結果を待つだけね」
Ｃ問題とＧ問題は、いわゆる“探索”と呼ばれるジャンルの問題だ。
探索問題の最大の特徴は、計算量のオーダーはおろか、いったいどのくらいの時間で計算が終了するのか、大雑把にでも見積もるのが非常に難しいことにある。
タマキとあたしは、まず、ＣとＧについて、ジャッジの用意したテストケースくらいなら全て通るであろうという程度のプログラムを作成した（これは自然な枝狩りをいくつか入れたらすぐに達成できた。ＴＬＥにならないことの確認には、もちろん“食道デバッグ”を使った）。
そして、そのプログラムをトウコに読ませ、２人の書いたプログラムがＴＬＥ（または
最後に、タマキとあたしが、トウコの作った撃墜ケースを含めて、どんな入力が来てもＴＬＥ・ＭＬＥしないようにプログラムを改良する。
ジャッジに提出してわざとWrong Answerを連発したプログラムは、この改良後のプログラムに、特定のテストケースにだけ間違った解を返すようなコードを書き加えたものだ。
そして、その“特定のテストケース”は、タマキの＜
もちろん、あたしたちが仕込んだ意図的なＷＡは、代わりに追加されたトウコ謹製のテストケースには反応しないようになっている。
すると、リジャッジの結果はどうなるか。
「サクヤちゃん！ リジャッジ開始だって！」
先ほどの返信メッセージから、ちょうど５分が過ぎた。
リジャッジ自体は一瞬で終わり、最初の方で投げた大量のWrong Answerが、一斉に評価を反転させる。
Yes - Accepted.
Yes - Accepted.
Yes - Accepted.
Yes - Accepted.
Yes - Accepted.
Yes - Accepted.
無論、同じ問題で何度もAcceptedをもらったところで、完数が重複したりはしない。
とはいえ、これで＋２完で、合計８完。当然、ＣとＧのペナルティタイムの上乗せは全て無効だ。
さらに、この＋２完には、ただの２完だけに留まらない、大きな意味がある。
「チェックメイトよ。緋笠カズミ」
――――たった今、リジャッジが行われたことで、今までWrong Answerだった私たちのコードが、一斉にAcceptedになりました。
――――どういうことかは分かりませんが、私たちがこれまで主張してきた不具合が、解消されたということでしょうか。
――――どちらにしても、こうなった以上、公平を期すために、全チームのＣ問題とＧ問題のソースコードを、一斉にリジャッジにかけるべきではないでしょうか？
４：４３経過 【玉兎 】 ＡＢＣＤＥＦＧＩＪ ９/１０完
風船が割れる音、というものを、緋笠カズミは初めて耳にした。
無論、ただの風船が割れる音なら、何度も聞いたことがある。
だが、ここはＩＣＰＣのコンテスト会場で、今はコンテストが行われている真っ最中だ。
そこで、風船が割れるということは。
すなわち、完数が減った、ということに他ならない。
「何が、起きた……！？」
緋笠カズミの端正な顔が、驚愕に染まる。
突然、会場中に大きな音が連鎖的に鳴り響いたかと思えば、それまで上がっていた黄色の風船（Ｃ問題）と水色の風船（Ｇ問題）が、立て続けにいくつも消滅した。
風船が、割れた。
その事実を認識するまでに、カズミは、たっぷり数十秒もの時間を要した。
そして、ふと顔を上げ、順位表を見やると。
「馬鹿な……！」
現在の順位：
１位 【__________】 ＡＢＣＤＥＦＧＪ ８完 ペナルティ＋１１９０
２位 【玉兎】 ＡＢＤＥＦＩＪ ７完 ペナルティ＋８６１
３位 【ブレインネクサス】 ＡＢＦＨＩ ５完 ペナルティ＋４９５
今の今まで９完だったはずの【玉兎】のスコアが７完にまで転落し、
ついさっきまで６完だったはずの【__________】のスコアが、８完になっている。
いったい何が起こったのか、まるで理解できない。
反射的に、ノーネームの机の方に目を向ける。
すると、秋葉サクヤが、勝ち誇ったような顔でこちらを見返してきた。
自然、視線が交錯する。
そこがコンテスト会場である限り、優れたプログラマー同士の会話には、必ずしも言語によるコミュニケーションが必要とされない。視線に込めた強い意志。それだけがあれば十分だ。
濃縮された時間の中で、２人の競技プログラマーが、目と目だけで会話を交わす。
――おや。そこの
――く……。済まないが、ご教授願おうか。
――あら、簡単なことよ。ジャッジからの公式アナウンス、見てないの？
それを聞いて、カズミは自分のパソコンのディスプレイに視線を戻す。
風船が割れたことで呆然として気づかなかったが、確かにジャッジから全チームへの通達メッセージが、１件届いていた。
そこには、Ｃ問題とＧ問題について、全チームの提出コードのリジャッジが行われ、その結果に応じて順位が再計算された、とある。
――……なるほど、そういうことか。
――何？ どういうことか分かったの？ 言ってみなさいな。あたしが採点してあげるから。
――君達は、何かしらの
――何らかのが多すぎるけど、ま、おおむね会ってるわ。６０点てとこね。ちなみに、テストデータを入れ替えたのは、あんたにはまだ見せたことのない、タマキのスキルよ。
――無論だとも。
――あんたに速度で勝てないんなら、完数で勝てばいい。そのためには、緋笠カズミ、あんたの完数を減らすのが一番手っ取り早い。簡単な理屈でしょ？
――まさか、ＩＣＰＣで撃墜なんて真似をしてくるとはね。その発想力には、素直に感服するよ。自分のコードがChallenge Succeededされるなんて、TopCoderでも久しく味わったことのない経験だからね。
――ちっ、これだから赤白は。……ま、さっき、あんたが本気で驚いた顔を見れたからよしとするわ。写真に撮れなかったのが残念だけど。
――……それにしても、一つ気になることがある。
――何？ まあおおよそ予想はついてるけど、訊いてごらんなさい？ 今のあたしは機嫌がいいから、大抵のことは教えてあげるわよ。
――テストケースを修正し、リジャッジを誘導したこと。そこまではいい。……だが、君達は、なぜ私のコードを撃墜できるという確信を持てた？ それとも、そんな確証はなく、とにかく賭けに出てただ偶然勝っただけだとでも言うのかい？
――確証？ もちろんあったわよ。運否天賦も嫌いじゃないけど、勝つべくして勝つ方が、あたしの好みなの。覚えてる？ あたしが主催した、プログラミングコンテスト。
――ＵＴＰＣ、か。
――そ。誰かさんが圧倒的大差で１位になった挙句、あたしに向かって「君と競い合えなかったのは残念だな。また今度、コンテストの参加者という立場同士で闘いたいね」なんて腐れた台詞を吐いた輩がいた、あのコンテストよ。
――……なかなか手厳しいね。
――あたしがあれを主催した目的は、緋笠カズミ、あんたについて、いくつかの事柄を確認することだった。具体的には、コーディングの癖と、それから、＜
――まさか……！
――そ。そのまさか。あんたの＜解法解放＞は、与えられた問題に対する正しい解法を与えてくれる
――……確かに、Ｃ問題とＧ問題は、私のコードでは、最悪のケースに関しては解ききれないという自覚はあった。だが、一度Acceptedをもらえば、たとえ嘘解法だろうと問題ないのが競技プログラミングの世界だ。だから、
――ああ、まあ、基本的にはあんたの言う通りね。現に、ＯＢ/ＯＧの会主催のコンテストなんかでは、Wrong AnswerがAcceptedになることはあれど、逆はない、ってのが慣例だしね。でも、ＩＣＰＣの公式ルールには、そんなこと、ひとっことも書かれてないのよ。むしろあたしは、今回の処置の方がよっぽど公平に思えるわね。ほら。テストなんかでたまに、「出題ミスがあったので、この問題は全員正解にします」ってのあるじゃない？ あれだって結局、その問題に時間を注ぎ込んでしまった生徒が不利になるのは変わらないじゃない。だからね、ジャッジのミスが判明したなら、素直にAcceptedだろうがWrong Answerにしちゃっていいわけよ。分かる？
――はは。いっそ清々しいほどの詭弁だな。テストデータを改竄した張本人が、何を言うかと思えば。
――なんだ、ちゃんと分かってるじゃない。それで、どうする？ ジャッジにあたしたちを訴えでもする？
――いや、止めておくよ。ＩＣＰＣのルールに、悪意あるクラッキングを禁止する項目はあれど、
――あら。珍しくあんたと意見が一致したわね。明日は雪でも降るんじゃないかしら。
――はは。とにかく、今日は負けを認めよう。私の完敗だ。賭けのルールに則って、昨年奪ったチーム名は、君達に返還しよう。
――よろしい。この期におよんで、見苦しく足掻かないところだけは評価してあげてもいいわ。
――感謝するよ。それでは、敗者は去るとしよう。ＩＣＰＣ世界大会、頑張ってくれたまえ。
――ふん。言われなくてもね。……あ、そうそう。たった今、タマキが組んだＩのコードを、トウコが食道デバッグし終えたらしいわ。それじゃ、また縁があったら会いましょ。
秋葉サクヤが目をそらし、視線での会話が途切れる。
その間、わずか２秒。
直後、ノーネームの机の上に、Ｉ問題を解いた証である黄緑色の風船が浮かび上がる。
これでノーネームは、ＡＢＣＤＥＦＧＩＪの９完。
一方で、玉兎の完数は、サクヤの策略によって７完にまで落ち込んだ。
「ああ……。２完差というのは、ここまで絶望的な違いだったのだな」
緋笠カズミは、そう、ぽつりと呟いた。
４：４６経過 【世界一 】 ０/１０完
「……驚きました。まさか本当に、あの緋笠カズミが、ノーネームに敗れ去るなんて」
風船が割れた瞬間、何が起こったのか。ノーネームが何を考え、何を実行に移したのか。
それらは全て、
ノーネームが逆転の刃を振り下ろすタイミングも、実に絶妙だった。
これが３０分も４０分も時間が残っているときの出来事であったなら、緋笠カズミほどの腕の持ち主なら、風船を割られた所から巻き返しを図ることも余裕でできただろう。
しかしもう、残り時間はわずか十数分だ。
改めて、ノーネームが入れ替えたテストケースに対応するようにＣまたはＧのプログラムを書き変えようにも、カズミにしてみれば、加えられたテストケースがどういった種類のコーナーケースなのか確かめている時間はない。
そうなれば、あらゆる入力に対応できる、きちんとしたプログラムを組まなければいけなくなり、とても今から２完を稼ぐには時間が足りない。
＜
カズミも同じようにリジャッジを請求して通ったとしても、ノーネームのコードを撃墜できるとは到底思えない。可能性があるとしたら、ノーネームがＤを単純なダイクストラ解法で通していた場合だが、彼女らがあらかじめこの撃墜作戦を見越していたとすれば、そんなわざわざ隙を作るような真似はしないだろう。
と、そこまで考えて、ふと、以前トオルが呟いた言葉を思い出す。
――あなたは、ノーネームが優勝できる可能性は、どのくらいあると考えているんですか？
――そうねぇ。五分五分、ってところかしらねぇ？
アイチにしてみれば、ノーネームは勝つべくして勝ったように見えるが、それでも勝率は五分五分だったらしい（絵空トオルの、競技プログラマーを見る目は実に正確なのだ）。
確率５０％の賭けに勝った挑戦者に、素直に称賛の拍手を送りたいと思う。
「あら？ アイチちゃん、その顔は、何か大事なことを勘違いしているわねぇ？」
「……？ 勘違い、ですか？」
「もしかして、もうコンテストは終わった、なんて考えてるんじゃないかしら？」
「……ええ。だって、もう事実上の決着はついたでしょう。ブレインネクサスは緋笠カズミの＜
そう言ってから、気づく。
「まさか、トオルさん。今からコンテストに参加する気なんですか？」
絵空トオルは、多くの競技プログラマーから、畏怖と敬意を込めて、そう呼ばれている。
全世界の競技プログラマーの頂点に立つ彼女に色が無い理由は、既存のレーティングシステムでは彼女の実力を測れないからだとか、そもそもTopCoderを管理しているのが絵空トオル本人であるからだとか、様々な噂が絶えない（トオル本人はそのあたりの事情について語りたがらないため、アイチにも真相は謎）。
そんな彼女であれば、たとえ残り時間があと１０分を下回りそうな今この瞬間からコンテストに参戦したとしても、ぶっちぎりで１位を取れるだろう。
彼女の
「そんなことはしないわよぉ。だって、お姉さんが１位になっても、面白くも何ともないもの」
自分が１位になれることは一切否定せずに、とろけるような声で言う。
「お姉さん言ったでしょ？ サクヤちゃんたちノーネームが優勝できる確率は、五分五分だ、って」
「？ ですから、その五分五分の賭けにノーネームが勝ったから、今」
「違うわよぉ。残りの五分の方は、カズミちゃんじゃなくてぇ」
トオルが言い終わる前に、アイチは、順位表に現れた、とある変化に気づく。
先ほどの風船が割れた爆音の嵐に比べれば、実に静かな、ある変化。
しかし、その一見さりげない変化は、コンテストの流れを、激変させる。
まるで、今までの全ては、しょせん予定調和だったとでも言うかのように。
「これは……、一体……！」
「だからぁ」
当然、その変化も予想していたとばかりに、絵空トオルは口を開く。
「サクヤちゃんがカズミちゃんにやったのと同じことを、今度はノーネームがやられちゃったのよぉ」
（No.3/3につづく）
Permalink | コメント(0) | トラックバック(1) | 00:03