CODE VS 4.0 参戦記
CODE VSに参加しよう
CODE VS 4.0(https://codevs.jp/)に出場してきました。
知らない方のために説明すると、CODE VS(コード バーサス)とは、
「ゲームのAIをあらかじめ作って持ちより、みんなで戦わせるプログラミングコンテスト」。
年に1回の恒例行事で、4.0 という数字が示すとおり、これが4回目の開催です。
本来であれば、1000人近い予選参加者が1ヶ月以上かけて競い合って、上位8人のみが決勝に出場できる狭き門なのですが、
今回の自分は、それとは別枠の「エキシビジョンマッチ枠」での出場です。
エキシビジョンはこの枠の参加者同士どうしで戦うのですが、ここで優勝すれば、
本選8名中から選ばれた優勝者と戦うイベント戦を行うことができます。
運営サイドから自分に、「エキシビジョンマッチに出てみませんか?」とメールが来たのは、
AIのプログラム提出締め切りの約1週間前。
どうも、色々な人に声をかけているようですが、自分が最後だったようです。
それから、もろもろの調整とか、突然言われてもこっちにも事情がとかいろいろあって、
実質的に作業ができるのは休日が丸1日分だけ。
これどうしろと?
AIを開発しよう
文句を言っていても仕方ありません。開発に取り掛かります。
それに、自分の知るかぎり、こういう1人だけ圧倒的に不利なシチュエーションに放り込まれた人物は、
たいていの場合において勝利していたような気がします。明確な勝ちフラグだと言えるでしょう。
今回のゲームは、いわゆる「戦略ゲー」です(https://codevs.jp/gamerule.html)。
村を建てたり、資源を回収したり、戦闘ユニットを生産したりして戦い、先に相手の城を落としたプレイヤーの勝ちです。
もとより時間はないので、全てにおいて完璧な対応をするプログラムを書くことはハナから不可能。
選択と集中。もっとも重要なルールを見極めることこそが、勝利へのカギです。
そして、具体的な詳しいルールはこちら(https://codevs.jp/assets/files/codevs4_rule.pdf)。
読んでみましょう。どこがもっとも重要なルールか分かりましたか?
正解はこちら。ご丁寧にも太字で書いてくれていますね。
このコンテストのAIには、自分で名前をつけられる。
これこそが、一般のプログラミングコンテストに比べて、CODE VS 4.0が決定的に優れているところであり、
同時に、勝敗を分ける分水嶺となる、超重要ポイントでもあります。
プログラミングに限った話ではありませんが、「命名」の果たす役割は、とにかく重大です。
名をつける、それはすなわち、内実を縛り、存在を規定すること。つまりは命を与える行為そのものと言っても過言ではありません。
分かっている人には今さら説明するまでもないことですが、プログラミングにおいても、名前をつけることは極めて重要です。
このブログ(http://d.hatena.ne.jp/shunsuk/20110926/1317033011)によると、プログラミングは「名前」が9割。
このブログ(http://ryo021021.hatenablog.com/entry/2013/10/31/145922)によると、コードを美しく保つには、命名に妥協しないこと。
このブログ(http://d.hatena.ne.jp/r-west/20090510/1241962864)によると、適切な名づけに徹底的にこだわることこそが、良いコードを書くために必要な、たったひとつの方法。
つまり、今回のCODE VSでも、AIの名前の出来によって、勝負の90%は決まるも同然なのです。
《AnagMars》へと至る道
自作のAIに名前をつける機会なんてものは、普通の人が日常生活を送っていても、そう多くはないと思います。
であれば、「AI」にとらわれず、技名や能力名、自分の二つ名をつけるつもりで命名してみてはどうでしょうか。
王道の、漢字+ルビタイプで行くとして、例をあげるなら、
《愚王の采配》
死の舞踏〜ダンス・マカブル〜と、ダイスをかけて。もちろん采配の「采=賽」ともかかっている。最近このルビと同名の小説が出てしまったので、たとえ考えたのは自分が先でも世間的にはパクリなのがネック。
《終焉》
「お前には認識できなかっただろうが……、今の一瞬で戦況は覆り、既に勝敗は決している」的なイメージ。漢字とルビの長さのアンバランスさが魅力。糸とイットがかかっているのもポイント。
とか、こんな感じの名前が、1つのパターンとして考えられると思います。
とはいえ、ここで致命的な問題が。
漢字使用不可。カタカナ・ひらがな使用不可。ほぼアルファベットと数字限定。
かっこいい名づけに極めて長けた、日本語という言語、まさかの完全封殺です。
これは痛い……。この制約に、多くの人が苦しんだだろうことが容易に想像できます。
であれば、《Unlimited Limit Ed》とか、尖った字面で攻めてみましょうか。
最初はこの路線で考えようとしました。しかし、予選の課題だった敵AIたちの名前を見てみると、
gelb, grun, lila, rosa, schwarz, zinnober, silber
と、どれも方向性が全く違います。
いくらキレキレに尖った名前をつけたところで、それで周囲の世界観(※誤用の方)から浮いていては本末転倒。
それは例えるなら、《アクセル》《プラズマ》《ボンバー》《ジェット》という二つ名を持ったヒーロー集団の中に、1人だけ《冥王》が混じっているようなものです。
尖りすぎると、かえって咎る。
いくらエグゼキューショナーがかっこよかったとしても、ただかっこいいだけで周りの命名との調和が取れていなければ、台無しになってしまいます。
かっこよさを追求すれば他から浮いてしまい、他との調和をとろうとすれば魂のこもった名前にならない。
この二律背反を解消できず、多くの参加者が涙を呑んで消えていったことと思われます。
しかし、自分クラスのプログラマーともなれば、この程度のアンチノミーなど恐るるに足りません。
字面に凝れないのなら、意味で凝ればいい。
人は見た目が9割などと言いますが、名前は見た目と中身が密接に関わりあっていて、
あえて片方をシンプルにすることにより、もう片方のこだわりが強調される、なんてことは、ざらに起こりえます。
自分は、それを利用して、
《AnagMars》(読み:あなぐまーず)
今回のAIに、この名前をつけました。
《AnagMars》にこめた想い
まずは「穴熊」。
イタチ科アナグマ属の動物のことではなく、将棋の穴熊囲いのことです。
CODE VS 4.0の戦略ゲームにおいて、自分の城の周りに大量のユニットを生産し、鉄壁の守りを築く。
壊されても壊されても、何個だって鉄壁を生成し続ける。
そうした戦略と「穴熊s」のリンク。
これが、《AnagMars》にこめた第1の意味です。
次に、マーズ(Mars)。
火星そのものではなくて、その命名の由来となった、ローマ神話やギリシャ神話の神のほうです。
このあたり、実は若干複雑なのですが、すごく端的に言うならば、マーズは戦と農耕の神です。
CODE VS 4.0で、ただ鉄壁を築くだけではなく、攻撃ユニットを送りこんで資源マスを制圧し、自軍はそこから恵みを享受する。
そうした作戦と、神マーズの名のリンクが、《AnagMars》にこめた第2の意味です。
わざわざMarsのMを大文字にしているわけで、ここまでは誰でも気づくと思いますが、続いて第3の意味。
《AnagMars》は《Ars Magna》のアナグラム。
アルス・マグナ。
響きのかっこよさもさることながら、錬金術の秘法だったり、世界の真理を解明する手段だったりと、その設定にもめちゃめちゃ心揺さぶられます。
だからこそ、様々な創作物の中でも、直接的・間接的にモチーフにされることが多いアルス・マグナですが、
今回は、その中でもややマイナーな、ジェロラモ・カルダーノが著した、代数学の書物であるところのアルス・マグナが由来です。
この本にまつわる有名なエピソードが「数学者の決闘」。
名だたる数学者たちが、己の導きだした代数方程式の解法どうしを競い合わせてバトル。
殴り合いともスポーツとも違う、知で知を洗う数学競技。
その逸話が、コードを書いて競い合うCODE VSと、極めて良くリンクしています。
アルス・マグナという言葉自体のかっこよさ。
大文字小文字の場所まで完全に一致するアナグラム。
CODE VSの競技性とアルス・マグナの逸話の類似。
このすべてに気づける人となると、一気に全体の半分くらいまで減るのではないでしょうか。
ここでさらにアナグラムを活かすため、ラスト第4の意味。
CODE VSの「VS」と「アルスマグナ」。
これらの単語でGoogle検索すると、VSとアルスマグナをタイトルに含む、一時期そこそこ流行った、とある小説がヒットします。
具体的には、こういう帯のやつ。
未読の人のために簡単に説明すると、陽のあたらない雑魚キャラがヒーローに一矢報いる、強烈なインパクトを備えた作品です。
これは、まさに今回のCODE VSにおける自分のシチュエーションそのもの。
エキシビジョンマッチという日陰の戦い、圧倒的に不利な状況下にも関わらず、表の決勝を勝ち上がってきたヒーローを叩く。叩き潰す。
この強烈な意志と渇望こそが、自分が《AnagMars》という名前にこめた第4の、そして最大の意味です。
プログラムを完成させよう
ここまでのネーミングに要した時間、わずか30分。
これは、常日頃から命名について悩み考えている自分だからこそ、達成できたタイムだと思います。
普通の人なら、これを考えるのに半日とか1日とか、かかってもおかしくないはず。
プログラムの開発にかけられる時間が1日しかないなか、ここを短時間で片づけられた恩恵はあまりに大きいです。
しかも、名前を決めたことで、どういう戦術で戦えば、名前にふさわしいAIになるかが、かなりの部分まで見えています。
というわけで、コードを書きます。
書きます。
書きます。
気合いで書きます。
書きあがりました。
決勝戦を見学しよう
CODE VS 4.0 決勝戦当日。
正規ルートで予選を勝ち上がってきた8名が、リーグやトーナメントを戦っています。
詳しい展開は省略しますが、並みいる大学生や社会人を打ち破って優勝したのは、まさかの中学生。
なんという主人公体質。なんというヒーロー補正。
もし、エキシビジョンマッチを勝ち抜いた自分が、彼と戦うことになれば、
・30近いおっさんと、15才の中学生
・同じ中学、同じ部活出身
・CODE VS初回優勝者と、第4回優勝者。
・超攻撃型の戦術と、超守備型の戦術。
と、ありとあらゆる面で対比が効いた、宿命の一戦となります。
否が応でも、期待が高まります。
エキシビジョンマッチに出場しよう
《AnagMars》で戦いました。
負けました。
共通点も真逆の点もそんなにない、必然性とか全くない感じの相手に。
普通に。
しかも大差で完敗。
その後
自分を下した相手はそのままエキシビジョンマッチで優勝し、中学生くんと死闘を繰り広げます。
その圧倒的な制圧力をもって、6本先取の試合で先に5勝。かたや中学生くんはいまだ3勝。
誰もが結末を頭に思い描いたなか、中学生くんは何かしらの力的な何かに覚醒したのか、そこから立て続けに3連勝。見事勝利。
超盛り上がった。
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2012/06/14
- メディア: 文庫
- クリック: 61回
- この商品を含むブログ (20件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2012/10/13
- メディア: 文庫
- 購入: 1人 クリック: 21回
- この商品を含むブログ (9件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2013/03/14
- メディア: 文庫
- クリック: 1回
- この商品を含むブログ (8件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2013/07/12
- メディア: 文庫
- この商品を含むブログ (3件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2013/11/14
- メディア: 文庫
- この商品を含むブログ (4件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/03/14
- メディア: 文庫
- この商品を含むブログ (2件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/07/12
- メディア: 文庫
- この商品を含むブログ (3件) を見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/10/11
- メディア: 文庫
- この商品を含むブログを見る
- 作者: 望公太,029
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/11/14
- メディア: 文庫
- この商品を含むブログ (2件) を見る
- 作者: 望公太,029,斉藤健吾(TRIGGER ※本文イラスト)
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/03/13
- メディア: 文庫
- この商品を含むブログ (2件) を見る
学生プログラマ日本一決定戦 CODE VS
CODE VS公式サイト【http://codevs.jp/index.html】
ここ1ヶ月ほど、こんなものに参加していました。
2011/12/1から2012/1/6までが予選期間で、その参加者のうちの上位8名(ただし学生のみをカウント)が決勝進出。
そこから2012/1/13までに決勝用のプログラムを書き上げ、2012/1/14に決勝参加者8名のコードを互いに闘わせます。個人戦のトーナメント形式。で、ベスト8とベスト4と準優勝と優勝が決まります。
このCODE VSは、マラソンマッチ風の長期戦型プログラミングコンテストであると同時に、「優れたプログラミング技術を持つ学生を発掘する」目的で、日本の(主にIT系の)企業主導で行われた初めての大会でもあります。
予選に参加登録するときに「希望職種」とか訊かれますし。予選開始日に至っては12/1。なんて露骨
あと、決勝戦の日をセンター試験当日に被せてきたのは、形式的には学生全体を対象にしつつも、優秀な高校生は決勝の枠を食いつぶすのを防ぐ意味合いもあったのではないかと思いましたが邪推しすぎですかそうですか。
というわけで、自分がこの大会に出て何を考えて何をやったかについての簡単な報告記事です。
予選
予選ルール:【http://codevs.jp/common/data/codevs_rule.pdf】
とりあえず、前半の1〜40面は全ての敵出現マスの隣にレベル4ラピッドタワーを1〜2個建てれば、後半の41〜80面は適当にレベル0ラピッドタワーで迷路を作ったあと適当な個数レベル4ラピッドタワーに強化すればクリアできるので、全クリ自体は簡単。
埋め込み解を防ぐために生成される面はSubmitごとにランダムに変化する、なんてことが書いてありましたが、気にせず全クリコードを何度も送信して様子を見てみます。
与えられるステージや敵の入力データを収集、分析。
すると、敵に関する全データ、ステージのサイズ、全敵出現マスと全防衛マスの位置は常に固定であることが分かります。
また、毎回形を変えているマップも、よく見ると
22 18 //予選57面の例 ###################### #*...........#.g.....# #........*......#....# #....g.....*......*..# #...................## #.........#...*.#.*..# #g...................# #......*...*.........# #..........*.#...#...# #..#*............*.s.# #.#......#.#....#....# #..#...#.............# #.#s...........#.....# #.......#....#.......# #.........g.......#..# #....*..#g...*.......# #....................# ###################### //#は壁 .は床 *は壁または床のどちらかに変化
のように、ランダムに変わるとは言いつつも変わる地点の数はわりあい少数であることが分かります。
また、*が床に変化したときは、そこにタワーを建てれば壁とみなすことができます。
じゃあ手動で解けるじゃん目から鱗
というわけで、予選期間中はひたすら手作業で遊んでいました。
実際、ちゃんと動く完全自動タワー配置プログラムを組みあげた今となっても、大抵の場合において、自分のプログラムが出した解よりも優秀な解を手動で求めることができます。
これは人間が優秀だというより自分のアルゴリズム力がゴミクズなだけではないかとか思ったとしても言ってはいけない
もちろん、ハイスコアを目指すのであれば、手動とプログラムをうまく役割分担させることが必要なのですが、予選では学生の中で8位以内に入れれば十分なので、結局ほぼ手動だけで予選を乗り切ることに決めました。
より正確に言うと、とりあえず手動で遊んで様子を見ようと思って手を付けたら思いのほか楽しくて止められず気づいたら予選終了1日前だった
なお、自分の予選の成績である「総合4位、学生3位、スコア78952」は、手動で全力を尽くした結果かと言えばそういうわけでもなく、まだまだ手動だけで点を伸ばせる余地のある面が大量に残っています。
もし(時間がもっとあって)手動で行きつく所まで行っていたら、cos65535さんの103079に届くか届かないか、くらいの所までは行けていた気がします。
colunさんに宣戦布告しておきながら結局真っ向勝負しなかった自分は、Twitterリムられてブロックされても文句言えないレベル。
あ、あの……、本当にすみませんでした。
そういえば、この予選は優れたプログラミング技術を持つ学生を決勝に招待するのが目的だったはずなのに、釣れたのはただのヌルゲーマー。まあ仕方ない
というわけで、運営側に提出したコード類の中に堂々とshudo.txtが入っている偽アルゴリズマーは、ちゃっかり決勝へ。
決勝準備
決勝ルール:【http://codevs.jp/final_popup.html】
決勝戦は、マップや敵の入力データが予め与えられないという、予選とは打って変わってゲーマーお断りのルールで行われました。
ちなみに、決勝戦のルールが明かされてデモプログラムが配布されたのが1/9の20時。
ソースコードの提出締め切りであるリハーサルの開始時刻は1/13の14:30。
しかも1/11と1/12は何かと忙しいせいであまり開発時間がとれない。
予選のプログラムを流用しようにも大半の時間を費やしたのはshudo.txt。おいいいい詰んだ
仕方ないので、楽をします。
まず、「レベル0ラピッドタワーで迷路を築く」と「そのうち何個かをレベル4まで強化する」の2つの処理を分離して、独立に考えます。
手動でやっていた時には考えられない暴挙ですが、この両方を同時に最適化するアルゴリズムなんて難しくて思いつきません。もしくは実行時間がかかりすぎる。
最初のステップ。迷路作り。
とはいえ、まともに迷路を作るのは実装が大変なので、敵の進路を妨害するように塔を建てることを考えます。
具体的には、次のようにします。
まず、防衛マスを1つを残して上下左右を全封鎖。
そして、残った防衛マスまでの距離が最短な敵出現マスを選び、下図のように、敵が出現してから1歩先の場所に塔を建てます。建てられない場合は2歩先、3歩先、……と候補を後ろにずらしていきます。
これを、もう塔が建てられなくなるまで繰り返します。
実際にはいくつかの改良を加えていますが、基本はこれです。
これに若干のランダムを入れて何度も繰り返して、もっとも性能の良い迷路を選びます。
焼きなまし、というか、適当に点を選んでそこの値を調べているだけも同然の行為なので、手動の性能には到底およびません。山すら登ってねえし
ちなみに、迷路の評価は、敵出現マスから防衛マスまでの距離の最小値が大きいものを優れた迷路としました。
これも手動では考えられない酷い近似ですが、この最小値と迷路の良さにはかなり強い正の相関があるので、シンプルにこれを採用します。
でも、蓋を開けてみると、決勝に参加した8人が8人とも、自分の迷路に匹敵するまたは劣る迷路しか作れていなかった気がするので、手動が封じられると現実的にはこのあたりが限界という説はあります。
次のステップ。塔の強化。
こちらでは、最大強化にしたときの射程範囲内をなるべく長く敵が歩くようなラピッドタワーから順に最大強化していきます。
シミュレーションしながら、ノーダメージで敵を全滅させられるようになるまでこれを繰り返します。
フリーズタワーは先のレベルの状況が分からない決勝では使いづらいので放置します。
アタックタワーは元々いらない子なので無視します。
ここまで組むのに約5時間。
あとは、15時間ほどかけて、この両ステップを高速化することに心血を注ぎました。
元と等価なプログラムを保ったままでの高速化だけではなく、若干スコアが下がることを覚悟しての高速化や、たまに建てられない所に塔を建ててしまうけれど大抵の場合は大丈夫、みたいな高速化までやりました。
なにせ決勝は、相手よりも処理時間が1ms遅れるごとに1money減点されるルールなので、プログラムの高速化は非常に重要なのです。
1回1回の試行が速ければ、ランダムに試せる回数も増えて、良い迷路が見つかる可能性も上がりますし。
労力をかけた甲斐あって、結局、他の決勝参加者と比べて時間面で優位に立てるプログラムを組むことができました。
ただし、その代わり、ある重要な処理を組み込むことをすっかり忘れていました。
全ての塔を最大強化してもなお致死量のダメージを受ける場合は、フリーズタワーを使ったり、そのレベルに特化した迷路に新しく組みなおしたりして、金に糸目をつけずにライフを守る必要があります。
決勝のゲームバランスでは、30面を超えたあたりでちょっと狭いマップ(それなりの確率で出現する)が出るたびに、塔を最大強化しても足りなくなってしまいます。
なのに自分は、このことをすっかり忘れていました。
時間がなくて組めなかったと言うよりは、時間がなかったせいで、これを組む必要があるということがすっかり頭から抜け落ちていました。
そんな致命的な欠陥を抱えたプログラムを提出してしまったことに気づかぬまま、決勝本番へ。
決勝戦
決勝会場にて、CUTEGさんとPOPさんのイラスト入りクリアファイルをゲット。
これらは非売品で、これだけでCODE VSに参加した価値は十分にあったと言えます。
どのくらい十分かと言うとn<=300の単一始点最短路問題ならワーシャルフロイドで十分なくらいに十分
さて、いよいよ決勝トーナメントの開始です。
8人の参加者が箱の中(見えない)からボールを引いて、トーナメント表の位置を決めました。
まずはベスト4決定戦。どの闘いも、勝者と敗者のプログラムにはあからさまな性能差があり、8人のうち下位4人が順当に敗退したといった感じでした。
次にベスト2決定戦。どちらの闘いも、勝者と敗者のプログラムには有意な性能差があり、4人のうち下位2人が順当に敗退したといった感じでした。
これが起こるのって相当に珍しいですよね?
実力が同じ人物はいないと仮定して計算してみたところ、確率は約15.2%。
なんだそこまで珍しくもないのか。どっちだよ
あとまるで関係ないけど%の直後に句点をつけるとパーミルに見えるね。15.2‰とかレア
そして決勝戦の中の決勝戦、優勝とその他大勢を分ける最終決戦が始まります。
かたやjellies(自分)、かたやyuukiさん。
yuukiさんのプログラムのこれまでの闘いを見たところ、または本人から直接話を聞いたところによると、yuukiさんはどうやら真面目に迷路を作っている模様。
「敵が歩くルート上に塔を建てる!」というだけのワンアイデアで最後まで走りきった自分とは違い、敵が通るルートをベースに考えてアルゴリズムを固め、複数の敵出現マスの合流地点をプログラムで陽に制御したりとかまでしていたようです。なにそれ組める気がしない
さらにyuukiさんは、全ての塔を最大強化してもなお敵を全滅させられないときは、ラピッドタワーをフリーズタワーに変えたりレベルごとに迷路を組みかえたりするといった処理まできちんとプログラムに組み込んでいるようでした。そう、自分が完全に忘れてたアレです。
事実、ベスト2決定戦(どちらの闘いも同じマップを使って行われる)では、自分がライフ0になって死んだ非常に狭いマップの43面をyuukiさんはクリアしています。対策してないのとしているのを比べればさもありなん。プログラムの根本性能に差がありすぎます。
リアルに、CODE VS!!―正義の味方を倒すには状態。
はっどうせyuukiさんとか勝てるわけないのに皆ムキになっちゃって馬鹿じゃねーの
だがちょっと待ってほしい。
VSでは、悪の戦闘員はヒーローのうち1人を沈めることには成功したのではなかったか。
召喚された瞬間に負け確だとしても、ヒーローに変身カードを使わせる暇を与えずに、数の利を活かして攻め続ければいいのではなかろうか。
そう。 狭 い マ ッ プ が 出 現 し な い こ と を 祈 れ ば い い
必死に。
ラッキー・ストライプを3積みし、太陽を連想するカードを全て排除したデッキを胸に、いざ決勝の舞台へ。
と言ってもプレイヤーに出来ることはただ見てるだけなんだけどな。開発初期のポケモンみたい
ばとるスタート。
敵の進行を妨害する位置に塔を建てるだけというシンプルなアルゴリズムが功を奏したのか、それともRuntime Error死のリスクを覚悟で行ったプログラムの高速化(&ソースの煩雑化)にかなりの時間を費やしたおかげか、自分のプログラムはyuukiさんのそれと比べて圧倒的に速いです。
決勝ルールにより、かかった時間の差分のお金が、1msあたり1money、yuukiさんの所持金からガリガリ削られていきます。
5000money差がつき、10000money差がつき、ほぼ1面分の資金差が開きます。
あとはこのまま、簡単な面が出続けてくれれば、順当に相手の資金切れで勝利できます。
だが・・・出るっ・・・!
40面を過ぎて・・・狭い面・・・!
瓦解。転落。焦燥。めのまえがまっしろになった!
なんせ、狭い面に対して相当の対策を施してきているyuukiさんと違い、自分のプログラムはただ塔を最大まで強化するだけです。
まさに敗色濃厚。圧倒的絶望感。いくらmoneyが残っていようと、相手より先に初期ライフ10がゼロになってしまえば何の意味もありません。
でも。
ここまでの不利が重なっておきながら逆転できないなんて、嘘だろう?
というわけで、ここで要素の相対論の神様降臨。
「まさか、
狭い面が終了した段階で、度重なる敵の猛攻を10あったライフを7も残して余裕でしのぎきったyuukiさんに対して、自分のライフは、残り1。
だがギリギリだろうと何だろうと耐えてしまえばこっちのもの。
あとは何面か簡単な面が淡々と続き、yuukiさんの資金が先に底を尽き、この闘いは自分の勝利で幕を閉じました。
生存戦略、外道上等。
決勝アフター
勝ったあああああああああいやっほうううううううううううう!
闘いの後は、表彰式だったりインタビューに答えたり懇親会だったり打ち上げだったり。
他の参加者たちの話を聞いて、新しい発見の数々に、目から鱗の連続でした。
具体的には、こんな感じ。
自分「自分の環境で動いていたプログラムが本番環境で動かなかったので、何がマズいのかと思ったらCygwin絡みのDLLが本番環境になかったのが原因でした。なのでソースとdllファイルを一緒に提出して動かしてるんですよー」
他の参加者「それ毎回DLLを読みに行くから遅いですよ。-mno-cygwinつけてコンパイルすると2倍くらい速くなりますよ」
何・・・だと・・・!?
自分「予選ではまず全クリできるプログラムを書き上げて、それを何度も提出して得られた入力データを統合することで、面や敵のデータを解析しました」
他の参加者「それデモの実行プログラムを逆コンパイルすると一瞬で入手できますよ。Javaだから簡単だし」
何・・・だと・・・!?
自分「他の人がどの面でmoneyをいくら消費しているのかの詳細なデータが欲しかったですね。あのmoneyの推移グラフは荒いので、1ドット単位で解析しても正確な値は得られない」
他の参加者「それデモプログラムとサーバーがやり取りしているデータを直接取得すれば普通に分かりますよ」
何・・・だと・・・!?
他の参加者「そもそもなんでcygwinで-O3なんて使ってるんですか?」
自分「いや……詳しいことは全然分からないんですけど……。普段アンダースコアーズで偉い人がそれでコンパイルしているので…………」
みたいな。
特に最初の会話、5時間かけてコードを煩雑にしてバグ混入の高いリスクを負ってまで迷路生成の速度を2倍にした自分の努力とは一体なんだったのか。
なんかもうね。自分だけ場違いな所に来ている感が甚だしかったね。
学生プログラマ日本一決定戦のはずなのに、なんでプログラムに詳しくない人が決勝に居んの? 的な。
自分マジアウェー。
なにせ、懇親会で様々なスポンサーor主催企業の方とお話する機会があったのですが、その中で一番盛り上がった会話が、Pixivの方との
Pixiv「優勝おめでとうございます」
自分「ありがとうございます」
Pixiv「クリアファイルは受け取って頂けましたか? あれ非売品なんですよ」
自分「はい。大切にします。CUTEGさんいろんな所で活躍してらっしゃいますよね」
Pixiv「そうですね。最近は講談社の出してるライトノベルとかでも」
自分「彼女がフラグをおられたら、面白いですよね。きれいな竹井10日先生とか新鮮で」
から始まる一連の会話だったくらい。
韓国の絵師さんをよく見るようになりましたよね、光の魔術師の方とかおいおいVOFANさんは台湾じゃねえかHAHAHA〜.的な。
これ絶対プログラマーの会話じゃねえ
さらにこの後の飲み会では、決勝参加者や運営側の人間が集まって、様々なトークに花を咲かせていました。
プログラマーの飲み会らしく、好きな言語とか、マニアックな言語仕様とか、最新の開発環境についてとか、各種IT系企業の良い所や不満とか、そういう話ばかり。
もちろん全然ついていけませんでしたが何か
学生プログラマ日本一だけが、2位〜8位の会話においてけぼり。
客観的に見るとすっごい面白い絵面なんだけどなんだこれ。
自分マジぼっち。ひとりがすきなボッチの、ともだちは、じぶんひとり
これは2期OPで一人だけ(笑)とか付けられて紹介されるレベル。
もしくは自分のニックネームを募集したらショーキン☆ドロボーとか名付けられるレベル。
まあ別にこの疎外感は今に始まったことではないですけどね。古くは高3のときの情オリ合宿から。
というか、そういう場でプログラミング言語について語るのは、数学オリンピックのメダリストたちが自身の愛用する鉛筆の特徴について熱弁をふるっているようなものだと思うんですがまあこれ言っても誰も納得してくれんよね
ところで、こういう場で成果を残した競技プログラマーがインタビューを受けるときの鉄板回答に「競技プログラミングそのものは実務に直接役に立たないが、そこで培われた問題解決能力を、現実の様々な問題を解くのに役立てていきたいです」というものがあるんですが、自分はこの答えがあまり好きではありません。
別にこの考え方自体を否定しているわけではなく、というかこう考えている人のことは立派だと思いますが、競技プログラミングというものにまず実務への応用ありきみたいなイメージがついてしまうのがなんとなく嫌なのです。
というわけで、これとはまた違った、しかし独り善がりにならず対外的なイメージも悪くない、競技プログラミングの魅力を新たなベクトルからアピールするような回答を用意していたのですがいざNHKにマイクを向けられると↑の鉄板回答を一字一句違わずに答えていた
まあNHKだからね。仕方ないね。
自分のような社会的弱者は長い者に巻かれておくのが基本
それとあれだ。とある参加者が「この3日間寝てない」とか言ってて、企業の方からも「皆さん頑張って徹夜で開発されてきたことでしょう」みたいなコメントがあり、寝ないのが当然みたいな雰囲気になっていたので、自分も「昨日は寝てません」と言っておいたのですが、実は8時間くらい寝てた。うわっ私の睡眠時間長すぎ
よく「寝ないで働いている人は有能」だったり、逆に「働きながらもちゃんと寝ている人は有能」だったり言われますが、作業効率の良さと寝ないでも作業できる能力の2つは別物なので、注意が必要です。
まあ自分は両方ないんだが
あと、インタビューで「優勝できた理由は?」みたいなことを何度か訊かれたので、その答えを重要な順に書いておくと、
(1)wataさんがCODE VSに興味を持たなかったこと
(2)chokudaiさんが運営側に回ったこと
(3)colunさんが学生ではなかったこと
あたりが主要因。
ちなみにインタビューでは(24)〜(26)あたりの理由を答えておきました。
それでも、yuukiさんは相当に手強い相手だったのですが、これに勝てた理由は、カブトボーグ的に言うならば9話で勝治が石田母に勝てたのと全く同じ理由。
うん!
まとめ
予選:ゲームやってた
↓
決勝準備:手抜き
↓
決勝:運
↓
アフター:ぼっち
まとめてみると想像以上にひどい
事実、他の参加者からは、言語設計の根底に流れる思想だとか説明会では聞けない企業の裏話だとか色々と有用な話を聞かせてもらった一方で、自分が他の人に与えられた知識はと言えば、「CUTEG」は
おい本当になんで参加したんだよこいつ
まあしかし、えてして世の中は不条理なもので、自分が「学生プログラマ日本一」の称号を獲得したのは事実。
そこで今度、競技プログラミング漫画が出版される暁には、是非とも自分をモデルにしたキャラクターを出演させて頂きたい。
具体的には、第1話で、「この方は学生プログラマ日本一のjelliesさんだぞ!」とか取り巻きに言われながら目障りな主人公に勝負を挑んで瞬殺される役回り。
ファイブレインで言うところの武田ナオキのポジション。
せめてそこはジーニアス奥寺くらいの立ち位置になりませんかね
CODE VSへの意見
こうした大会が開かれるのは初めてなのでノウハウが無かっただろうことや、chokudaiさんが参加するまで運営側に競技プログラマーとして優秀な人材がいなかったことなどもあり、この大会について参加者として不満を感じる点は多々ありました。
ですが、最終的には、決勝トーナメントは盛り上がりに盛り上がり、こうした競技に多少なりとも興味のある人ならば楽しめる大会になっていたと思います。私自身も非常に楽しめました。
また、競技プログラミングを幅広い層に広めるためにも、この大会は一役買えていたと思います。
運営側のみなさん、他の参加者のみなさん、本当にありがとうございました。
ただし最後に1つだけ。
決勝進出者が運営側に提出したソースコードを、企業の方にレビューさせるとか自殺行為以外の何物でもない
おわり。(就活と言い張ってタワーディフェンスばっかりやっていられた日々が)
(※本記事には、話を分かりやすくするため、若干の嘘と誇張や厳密でない表現が含まれている場合があります)
__________の ICPCアジア地区予選2011参戦記
この記事は、Competitive Programming Advent Calendarの25日目用に書かれたものです。
はてなダイアリーの容量制限のため、3記事に分割して投稿してあります。
(1) __________の ICPCアジア地区予選2011参戦記 No.1/3
__________の ICPCアジア地区予選2011参戦記 No.3/3
4:48経過 【__________ 】 ABCDEFGIJ 9/10完
「何なのよ……これ……」
あたしは、ただ呆然と、目の前の巨大な順位表を見つめていた。
「なん、で……?」
「…………」
タマキも愕然としている。あのトウコでさえも、表情が強ばっているのが分かる。
カズミを潰して、9完して、それで勝利確定だったはずなのだ。
なのにどうして、今、あたしは、これまでで最大級に、“負け”を確信している?
一体、なんで。
「どうして、【
ふらふらと定まらない視線で、すっかり様相を変えてしまった順位表に、目を向ける。
だが、何度見たところで、結果は同じ。
絶望に覆われた順位表は、あたしたちに敗北の現実を突きつけるだけだ。
現在の順位:
1位 【若葉】 ABCDEFGIJ 9完 ペナルティ+1614
2位 【__________】 ABCDEFGIJ 9完 ペナルティ+1615
3位 【玉兎】 ABDEFIJ 7完 ペナルティ+861
このコンテスト中、チーム若葉が、3位以内に入ってくることは、今まで1度もなかった。
確かに序盤はそこそこの速さで正確に問題を通していたけれど、それだけだ。
ついさっき順位表を見たときも、若葉の順位は、ブレインネクサスよりも下の、4完止まりだったはず。
それが、どうして、9完。
あたしたちを抜いて、9完。
「……サクヤちゃん! サクヤちゃん! しっかりして!」
「っ!」
気がつくと、あたしの身体は、タマキに肩を掴まれてがくがく揺すられていた。
……どうやら、茫然自失だったあたしを、タマキが正気に戻してくれたみたいね。
「……サンキュ、タマキ。おかげで我に返れた」
「うん。でも、どうしてこんなことになっちゃんたんだろう……」
タマキの言う、こんなこと。
その原因は、少し冷静に考えてみれば明白だった。
「サブマリン戦術。あたしたちは若葉に、それをやられた」
若葉は、ずっと4完で止まっていたんじゃない。ただ、問題を解いていたのに、それを
ABFDの4問を、ペナルティタイム+184で通した若葉は、その後の時間を使って、ちゃんと問題を解いていた。
そして、溜まった5問のソースコードを、ノーネームのペナルティタイムを上回れるギリギリの時間で一気に提出した。
+286×5=+1430。これに+184を足して、+1614。
まさに、
「くっそ……! 完全に計算外だった……!」
一見すると、サブマリン戦術は、自分のチームのペナルティタイムを増やすだけで、何のメリットのない作戦のように見えるかも知れない。
だが、それは大きな間違いだ。
ICPCは、できるだけ高い成績を取る競技ではなく、少しでもいいから他のチームより高い成績を取る競技なのだ。
たとえば、安全に100%7完できる戦術と、80%の確率で6完止まりだが、20%の確率で8完できる奇策があったとしよう。ここで、他のチームが高々6完しかできないと分かっていれば、何の迷いもなく安全策を取ることができる。
ゆえに、他のチームの動向を知ることは、自分のチームの戦略を立てるうえで非常に重要になってくる。
そして、普通なら、他のチームの動向は、順位表を眺めていれば大体掴むことができる。多少の誤差はあれど、大きく外すことはまずない。
ただ1つ、サブマリン戦術という例外を除いては。
「どうするの、サクヤちゃん!? もう時間がないよ!」
分かってる。全ては、カズミを潰したうえで9完できれば全てが終わるという間違った見積もりを立てたあたしの責任だ。
若葉の作戦は、本当に見事としか言いようがない。
あたしたちに潰されたカズミと、カズミを潰すためにかなり余計な時間を消費したあたしたち。
両者が争っている間は巧妙に身を隠し、最後の最後で全ての利益をかっさらう。
ああ……。もう、本当に、戦略家としては完敗だよ……!
――サクヤ先輩にそう思っていただけるなら、私たちの頑張りも無駄じゃなかったんだなって、そう思えます。
ふと、視線を感じて振り向く。
今まで注意を向けることもなかった、あたしたちの後ろ斜め後方の机。
チーム【
――先輩を騙すような形になってしまって、ごめんなさい。けど、私たちが勝つには、こうするしかなかったんです。
ああ、分かってるよ。
途中、もしあんたたちが目立った活躍を見せてたら、カズミは容赦なく若葉を潰しに行った。
悪いとは思うけど、多分あたしだってそうしただろう。
――私たち3人が
それも分かってる。
サブマリン戦術は、誰にでもできる闘い方じゃない。
潜伏している以上、サブミットの結果を見てのデバッグは一切行えない。
いざ浮上ってときに、1つでもWAを出してしまえば、あたしたちにペナルティタイムで負けてジ・エンド。
あたしらみたいに、“食道デバッグ”なんてものも無いのに、ここまで大胆な戦術を実行に移せるその正確無比なコーディング力と胆力は、あたしにはないものだ。尊敬する。
あんたたちは、
――2年前、まだまだひよっこだった私たちを、サクヤ先輩は優しく導いてくれました。そのとき、私たちは思ったんです。ああ、この人のようになりたいな、って。先輩のような、強くて、温かくて、そしてカッコいいコーダーに。サクヤ先輩は、ずっと私たち3人の憧れの存在だったんです。
そう言ってもらえると、あたしも嬉しいけど。
ちょっと恥ずかしいけど、悪い気はしない。
――1年前のICPCには、私たちなりに努力して臨んだつもりでした。努力して、国内予選を突破できるところまで行きました。でも、それで初めて分かったんです。先輩のチームとあたしたちの間にある、圧倒的な力の差が。アジア地区予選で大敗した日の夜は、正直、ちょっと泣いちゃいました。こんな人たちを目指そうだなんて、あたしたちは、なんて無謀なことを考えていたんだろう、って。
でも、それで今のあんたたちがあるんでしょう?
――はい。それがきっかけになって、私たちは、覚悟を決めました。生半可な気持ちじゃ、サクヤ先輩の高みには届かない。スキルの1つも持たない私たち凡人が、高みに至るために、毎日毎日、考えて、練習して、闘って、反省して。ただひたすら、それの繰り返し。最初は全然成果が上がらなくて、何度もくじけそうになったけど。それでも、私たちは、ここまで来た。サクヤ先輩に、認めて欲しかったから。
ああ、認めるよ。
そんな姿を見せられて、誰が認めないなんて言えるかよ。
――ありがとうございます。その言葉だけで、私たちは救われます。……最後に、サクヤ先輩。先輩の、世界大会に行くっていう目標を、邪魔してしまって本当にごめんなさい。実を言うと、私たちは最初、+1616で浮上するつもりだったんです。先輩に次いで2位になれるなら、それで満足かな、って。
…………。
――でも、駄目でした。直前になって、どうしても勝ちたい! って、思ってしまったんです。先輩に並ぶだけじゃ、満足できなくなって。先輩を超えたい、っていう想いが、抑えきれなくなって。気がついたら、浮上のタイミングを、早めていました。……先輩。私たちは、尊敬する先輩の姿に、自らの手で傷をつけてしまった大罪人です。許してくださいなんて言いません。どんな裁きだって甘んじて受けます。だから、それでも、できることなら、私たちのことを
あのさあ、カエ。
――?
その“先輩”って、一体誰のこと言ってんのよ。
――え? サクヤ先輩?
あんたらの言う“憧れの先輩”ってのはさあ、ちょっと後輩に抜かれた程度で簡単に目標を諦めてしまうような、ヤワな野郎なわけ?
はっ。だったらあたしとは仲良くなれそうにないわね。無理。絶対無理。生理的に受け付けないわ。
――え、いや、あの、先輩?
命拾いしたわね、カエ。もしあんたたちが本当に+1616で浮上してたら、あたしはあんたたちを思いっきり全力でぶん殴ってたところよ。
――先輩、どうして……。
見てなさい、とは言わないわ。
今から汚いものをいっぱい見せるから、嫌なら目をつぶって震えていればいい。
努力は必ずしも報われないし、作戦は必ずしも実らない。
夢は必ずしも叶わないし、想いは必ずしも届かない。
現実は、必ずしも思い通りにはならない。
でも、とりあえずは、まあ、そうね。
――あんたらの思いあがった根性、このあたしが叩きなおしてやるから、覚悟しなさい。
この間、約3秒。
「タマキ! トウコ! この勝負、勝つわよ!」
無理やり意識を現実に引き戻す。
さっきのやり取りで、俄然やる気が出てきたわ。
「おぉー! サクヤちゃんが本気だよぉー!」
「サクヤ。次の作戦は」
今まであたしについてきてくれたこいつらのためにも、ここで折れるわけにはいかない。
信念も、目標も、そして結果も、何もかもだ。
チームメイト2人に向かって、あたしは、精一杯の悪い顔を浮かべながら、告げる。
「作戦? そんなものは無いわ。個人プレーの、力押しで行くわよ」
4:50経過 【__________ 】 ABCDEFGIJ 9/10完
「<
鈴の音のような澄んだ耳鳴りが、あたしの身体の中を駆け巡る。
何度やっても、慣れない感覚。けれど今は、この違和感を叩き伏せてコーディングするしか方法はない。
コンテスト終了まで、残り10分。
残されたわずかな時間の中で、H問題を通す。
あの“最強最速の双子”ですら15分かかった問題を、それより5分短く解く。
それしか、あたしたちが生き残る道はない。
考えてみれば、これは、去年のアジア地区予選と全く同じ状況だった。
約10分を残して9完するも、1位にいるのはペナルティタイムであたしたちを上回る【玉兎】。
残された強実装の構文解析を通せずに、そのまま敗北した。
同じ失敗を2度繰り返して負けるなんて、あたしのプライドが許さない。
あたしを相手に、10分も猶予を与えることが一体どういうことなのか。
きっちり教えてあげようじゃないの。
「
これで、あたしの主観では、ディスプレイが2つに、キーボードが2つ。
普段は扱いづらいスキルだけど、こんなときくらいは全力で活用させてもらう。
「まずは、関数プロトタイプ宣言!」
#include <stdio.h> #include <ctype.h> #include <string.h> int fexpr(int r1,int c1,int r2,int c2); int fterm(int r1,int c1,int r2,int c2); int ffactor(int r1,int c1,int r2,int c2); int fpowexpr(int r1,int c1,int r2,int c2); int fprimary(int r1,int c1,int r2,int c2); int ffraction(int r1,int c1,int r2,int c2); int fdigit(int r1,int c1,int r2,int c2); int vexpr[21][81][21][81]; int vterm[21][81][21][81]; int vfactor[21][81][21][81]; int vpowexpr[21][81][21][81]; int vprimary[21][81][21][81]; int vfraction[21][81][21][81]; char board[21][81];
ある領域を評価するためのの
構造は極力シンプルに。
実行速度が早くなくてもいい。多少の冗長さなら許容する。
とにかく正確に、紛れやバグの出ないコーディングができるよう。
全ての土台を、慎重に組み上げる。
「サクヤちゃん! あと8分だよ!」
<
そのうち2つずつを、仮想のディスプレイAとキーボードAに。
残った2つずつを、仮想のディスプレイBとキーボードBに。
それぞれ割り当てて、並列コーディングを開始する。
<仮想ディスプレイ A> bool allspace(int r1,int c1,int r2,int c2){ for(int i=r1;i<r2;++i) { for(int j=c1;j<c2;++j) { if(board[i][j]!='.')return false; } } return true; }
<仮想ディスプレイ B> bool allspace_col(int r1,int r2,int c1){ return allspace(r1,c1,r2,c1+1); } bool allspace_row(int c1,int c2,int r1){ return allspace(r1,c1,r1+1,c2); }
空白地帯の判定関数は終了。
デバッグやテストをしている時間は取れない。一発完動は大前提だ。
「サクヤ。残り7分」
拡張領域での作業は、あたしの主観では、2つのパソコンに同時にそれぞれ別々のコードを打ち込んでいるようなものだ。
だが現実では、あたしが2つのキーボードに打ち込んだ情報は統合され、1つのソースコードになって出力される。
つまり、1つのソースを書き上げるのに、2つの仮想的なキーボード入力を同時に使用しているのと同じ。
理論上には、コードが書き上がる速度は2倍。
コードが書き上がるまでにかかる時間は、半分だ。
<仮想ディスプレイ A> void shrink(int &r1,int &c1,int &r2,int &c2){ while(r1<r2){ if(allspace_row(c1,c2,r1))++r1; else break; } while(r1<r2){ if(allspace_row(c1,c2,r2-1))--r2; else break; } while(c1<c2){ if(allspace_col(r1,r2,c1))++c1; else break; } while(c1<c2){ if(allspace_col(r1,r2,c2-1))--c2; else break; } }
<仮想ディスプレイ B> #define mod(x) ((((x)%2011)+2011)%2011) int inv[2022]; int mypow(int x,int d){ int ret=1; if(d==0)return 1; if(d%2==1)return mod(mypow(x,d-1)*x); ret=mypow(x,d/2); return mod(ret*ret); } int main(){ for(int i=1;i<2011;i++)inv[i]=mypow(i,2009); for(;;){ int rows,cols; scanf("%d ",&rows); if(rows==0)return 0; for(int i=0;i<rows;i++){ gets(board[i]); } cols=strlen(board[0]); memset(vexpr,-1,sizeof(vexpr)); memset(vterm,-1,sizeof(vexpr)); memset(vfactor,-1,sizeof(vexpr)); memset(vpowexpr,-1,sizeof(vexpr)); memset(vprimary,-1,sizeof(vexpr)); memset(vfraction,-1,sizeof(vexpr)); printf("%d\n",fexpr(0,0,rows,cols)); } }
「ぐ……っ!」
唐突に、脳を針で刺したような痛みが襲う。
頭の中を貫かれたかのようなその鋭い激痛は、過剰な身体感覚が送り込まれてきた脳が、拒絶反応を起こしたことによるものだ。
「
いくら嘆いても、一度身についてしまったスキルの特性を変えることなどできるはずもない。
「
たまらず脳そのものを2倍にする。
それにより、頭蓋骨を開いて火箸を突っ込まれたような痛みは消えるも、その代わり身体が平衡感覚を全て失ってしまったかのように上手く動かない。動かせない。
感覚を統合する受け皿を増やしたことによる、混乱。
船酔いを20倍くらい酷くしたような、気持ち悪さが一挙に襲いかかってくる。
残り4分50秒。
だが、それでも、AとBのどちらか一方でもコーディング速度が落ちれば、待っているのは敗北。
身体を休めるわけにはいかない。思考を止めるわけにはいかない。
<仮想ディスプレイ A> #define HERE(x) (x)[r1][c1][r2][c2] int fexpr(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vexpr)!=-1)return HERE(vexpr); if(fterm(r1,c1,r2,c2)!=-2){ return HERE(vexpr)=fterm(r1,c1,r2,c2); } for(int j=c1+1;j<c2-1;j++){ for(int i=r1;i<r2;i++){ if(board[i][j]=='+' || board[i][j]=='-'){ if(allspace_col(r1,r2,j-1) && allspace_col(r1,r2,j+1) && allspace_col(r1,i,j) && allspace_col(i+1,r2,j)){ int ret1=fexpr(r1,c1,r2,j-1); int ret2=fterm(r1,j+2,r2,c2); if(ret1!=-2 && ret2!=-2){ if(board[i][j]=='+')return HERE(vexpr)=mod(ret1+ret2); else return HERE(vexpr)=mod(ret1-ret2); } } } } } return HERE(vexpr)=-2; }
<仮想ディスプレイ B> int fterm(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vterm)!=-1)return HERE(vterm); if(ffactor(r1,c1,r2,c2)!=-2){ return HERE(vterm)=ffactor(r1,c1,r2,c2); } for(int j=c1+1;j<c2-1;j++){ for(int i=r1;i<r2;i++){ if(board[i][j]=='*'){ if(allspace_col(r1,r2,j-1) && allspace_col(r1,r2,j+1) && allspace_col(r1,i,j) && allspace_col(i+1,r2,j)){ int ret1=fterm(r1,c1,r2,j-1); int ret2=ffactor(r1,j+2,r2,c2); if(ret1!=-2 && ret2!=-2){ return HERE(vterm)=mod(ret1*ret2); } } } } } return -2; }
構文解析の問題は、大枠さえ組めれば、後は
それぞれの機能は関数という形で並列に並べてある。実を言うならば、構文解析ほど並列コーディングに適したジャンルはない。
「サクヤちゃん! 残り3分10秒を切ったよっ!」
タマキの声色からも、この最後の勝負に参加できない歯がゆさが伝わってくる。
でも、<
加えて、能力発動中にもし誰かが
この領域で闘えるのは、正真正銘あたしだけ。
最後までワガママなリーダーで、悪かったわね。
でも、その代わり、この問題だけは、何があっても通すから。
<仮想ディスプレイ A> int ffactor(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vfactor)!=-1)return HERE(vfactor); if(fpowexpr(r1,c1,r2,c2)!=-2){ return HERE(vfactor)=fpowexpr(r1,c1,r2,c2); } if(ffraction(r1,c1,r2,c2)!=-2){ return HERE(vfactor)=ffraction(r1,c1,r2,c2); } if(c2-c1>=3){ for(int i=r1;i<r2;i++){ if(board[i][c1]=='-'){ if(allspace_col(r1,i,c1) && allspace_col(i+1,r2,c1) && allspace_col(r1,r2,c1+1)){ int ret=ffactor(r1,c1+2,r2,c2); if(ret!=-2){ return HERE(vfactor)=mod(-ret); } } } } } return -2; }
<仮想ディスプレイ B> int fpowexpr(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vpowexpr)!=-1)return HERE(vpowexpr); if(fprimary(r1,c1,r2,c2)!=-2){ return HERE(vpowexpr)=fprimary(r1,c1,r2,c2); } for(int i=r1;i<r2;i++){ if(fdigit(i,c2-1,i+1,c2)!=-2){ if(allspace_col(r1,i,c2-1) && allspace_col(i+1,r2,c2-1)){ int d=fdigit(i,c2-1,i+1,c2); int ret=fprimary(r1,c1,r2,c2-1); if(ret!=-2){ return HERE(vpowexpr)=mypow(ret,d); } } } } return -2; }
残り1分15秒。
くそ……! ペースが落ちてきてる……っ!
2つの脳が混ざり合ってぐちゃぐちゃになってしまったかのようだ。
体力が保たない。集中力が続かない。ただ意識を保つことがこんなにしんどいだなんて。
しかも、ここに来て、脳の痛みが復活しやがった。
やっぱり、どう工夫しようとオーバースペックであることに変わりはないのだ。
鈍痛と疼痛が同時に襲ってくる。何もかもを投げ捨ててこの痛みから解放されたいという衝動が、隙あらばあたしの身体を支配しようとしてくる。
マズい……このままじゃ、確実に……!
だったら!
「
ただでさえキーボードの操作だけで手一杯だった触覚を、一時的にとはいえマウスに回す。
余計に脳の回線が乱れに乱れ、普通に立っていることさえ困難になる。
だから、身体は捨てる。机に倒れかかるようにして、仮想の4つの目と4つの手だけに研ぎ澄ませた全神経を集中させる。
範囲選択。コピー。そしてペースト。
1つ1つの関数の構造には共通点が多い。
だったら、毎回一から打ち込むよりも、コピーしたものを修正した方がわずかに早い!
<仮想ディスプレイ A> int fprimary(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vprimary)!=-1)return HERE(vprimary); if(fdigit(r1,c1,r2,c2)!=-2){ return HERE(vprimary)=fdigit(r1,c1,r2,c2); } if(c2-c1>=5){ for(int i=r1;i<r2;i++){ if(board[i][c1]=='(' && board[i][c2-1]==')'){ if(allspace_col(r1,i,c1) && allspace_col(i+1,r2,c1) && allspace_col(r1,i,c2-1) && allspace_col(i+1,r2,c2-1) && allspace_col(r1,r2,c1+1) && allspace_col(r1,r2,c2-2)){ int ret=fexpr(r1,c1+2,r2,c2-2); if(ret!=-2)return HERE(vprimary)=ret; } } } } return -2; }
<仮想ディスプレイ B> int ffraction(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(HERE(vfraction)!=-1)return HERE(vfraction); for(int i=r1+1;i<r2-1;i++){ bool allhyphen=true; for(int j=c1;j<c2;j++)if(board[i][j]!='-')allhyphen=false; if(allhyphen){ int ret1=fexpr(r1,c1,i,c2); int ret2=fexpr(i+1,c1,r2,c2); if(ret1!=-2 && ret2!=-2)return HERE(vfraction)=mod(ret1*inv[ret2]); } } return -2; }
残り、20秒。
なのに、組むべき関数は、あと1つだけ残っている。
「くっ、そぉぉぉぉぉぉぉぉぉ!!」
腹の底から大声を捻りだして、もうほとんど麻痺して感じられなくなっていた拡張感覚を、無理やり引き戻す。
頼む。あとたった5行なんだ。それさえ保ってくれれば、後は――――!
int fdigit(int r1,int c1,int r2,int c2){ shrink(r1,c1,r2,c2); if(r2-r1==1 && c2-c1==1 && isdigit(board[r1][c1]))return (board[r1][c1]-'0'); return -2; }
あと4秒。
最後の1文字をタイプし終えたと自覚した瞬間、今まで辛うじて机に支えられて保っていたあたしの身体が、崩れ落ちて乾いた床の上に投げだされる。
あと3秒。
そんなあたしに、タマキが半泣きになりながら駆け寄って来るのが見える。
一方でトウコは、あたしの方には目もくれず、コードが組み上がった瞬間、
あと2秒。
そう、それで正解だよ、トウコ。
……でも、タマキも、ありがとう、な。
あと1秒。
意識がぶつ切りになって、<
急に感覚の半分が消滅したことで、身体全体を形容しがたい喪失感のようなものが埋め尽くし、蹂躙し、そして。
視界が、暗転する。
試合後
また、あのときの夢を見た。
「秋葉サクヤ。この勝負、お前の負けだ」
真っ黒なコートに身を包んだ長身の男が、抑揚を感じさせない声で、闘いの結末を告げる。
「……っ! はぁ……っ! 嫌だ……! あたしは、まだ、闘える……っ!」
当時まだ10歳だったあたしには、ただ吠える以外に何もできることはなかった。
それが、突然現れてあたしの日常を何もかもメチャクチャにした男に対する、精一杯の抵抗だった。
「喚くな、見苦しい。敗れた者には、何を望む資格もない。貴様は負けた。運命の歯車は、我が手の中にある」
「許さない……っ! お前だけは……絶対に……!」
「ほう。復讐を望むか。ならば、運命に抗ってみるか? 負けることは、死ぬことだ。その摂理を歪めてでも、生にしがみつこうとする小さき者よ。足掻け。足掻き続けたその先で、貴様の理想とする競技プログラマーの姿を掴んでみせよ」
「上等だ……! 待っていろ……。必ずお前を殺してやる……っ!」
「不可能だ、と言っておこう。だが、貴様がもし、競技プログラミングを以って運命の輪を捻じ曲げるに足る資格を持つ者だとすれば。……我は待とう。レーティング4000を超えた者だけが至ることのできる境地、
そしていつも、ここで夢は途切れる。
目が覚めると、ベッドの上だった。
「痛ッ……!」
身体を起こした途端、思い出したかのように激しい痛みが襲ってくる。
頭がずきずきと軋むように痛い。酷使しすぎた脳が悲鳴を上げている。
「ここは……。ああ、そういやあたし、コンテスト終了と同時に気絶したんだっけ……」
見慣れない部屋に寝かされているということは、おそらく、自分はコンテストのスタッフだか誰だかの手でここまで運ばれてきたのだろう。
時計を確認すると、午後7時。倒れてから、丸々5時間近くも寝ていた計算になる。
「ったく。これだから、あたしの
いくら一時的にコーディング速度を増すことができるとはいえ、並列コーディングの最中に味わう苦しみは、想像を絶するレベルだ。
それでいて、下手をすれば今のようにぶっ倒れてしまうとは、メリットとデメリットが釣り合っていなさすぎる。使い所が難しいにも程がある。
もっと使い勝手のいいスキルなんて、いくらでもあるだろうに。
「ま、今回はそれに助けられたわけだし、良しとしましょうか」
そう呟いて、そして、ふと思い出す。
「あ、そういや、あたし、コンテストの結果知らないじゃん……」
Hのコードを組み上げた瞬間、精根尽き果てて意識を失ってしまったが、よく考えるとあのコードが通ったのかどうか確認していない。
あのときは、自分の書いたコードがどれだけ正確に動きそうかの判断が全くできないほどの極限状況下だった。
通ったとしても、落ちたとしても、何らおかしくはない。
「……タマキかトウコに、訊いてみっか」
コンテスト中はあれほど勝利への執念にとりつかれたようになっていたにも関わらず、今は不思議と気持ちが穏やかだ。
おそらく、あの並列コーディングで、Acceptedにかける情熱的な感情のようなものを、一時的に全て燃やしつくしてしまったのだろう。
今なら、どんな結果を聞いても素直に受け止められる気がする。
携帯を取り出し、電話をかけようとしたところで、ギィ、と、少しサビついた扉が開く音がした。
「トウコ?」
そこに立っていたチームメイトは、とことこと歩いてくると、あたしが寝ている隣のベッドに腰を下ろした。
今ごろは
とはいえまずは、結果を訊かねば。
「ねぇトウコ。コンテストの結果、どうだった?」
単刀直入に、訊ねる。
それに対して、トウコは、言いずらそうに俯きながら、ぽつり、と。
「……サクヤ、ごめん」
ごめん、ということは、そういうことなのだろう。
「……はぁ。ま、覚悟はしてたけどね。あんな綱渡りみたいなコーディング、成功する方がどうかしてるわ」
それがあたしの本心からの言葉だったかと言われれば、即答することはできない。
でも、不思議と今のあたしは、全力を尽くしたんだから悔いはないなんて、そんな似合わない考えを自然と受け入れられているような、そんな気がするのだ。
「心から反省している。次こそは」
「次は、って、もう来年の話? そもそも、別にあんたの責任じゃないわよ」
「でも、私がもっとしっかりしていれば」
「あー、うるさい! あんた、あたしが湿っぽいの嫌いだっての知ってるでしょ? あたしたちが負けたのは、誰の責任でもない。しいて言うなら、みんなの責任。異論は認めない」
「……サクヤ、ありがとう」
ゆっくりと頭を下げたトウコは、それから、おずおずとあたしに何かを差し出してきた。
それは、プラスチック製の、比較的大きめのタッパーだった。中身は空。
ただし、タッパーの内側には、茶色いソースらしきものが少し付着していて――。
「閉会式に出た料理を、サクヤにも食べさせてあげようと思い、この中に詰めた。一杯に詰める所まではうまくいったが、ここに来る途中で、少しくらいなら歩きながら食べてもいいかと考え、蓋を開けたはいいが……5メートルと保たなかった。心から反省している。でも、私の責任ではないとサクヤが言うのなら」
殴った。
グーで。
「な……っ! 残像だと!?」
「サクヤは甘い。1つ1つの動作が直線的すぎる」
あたしの拳を避けたトウコは、重力を感じさせない動きでベッドから立ち上がると、いつものような無表情でこちらを見つめてきた。
「なお、閉会式の料理は、主に私が食べつくしたおかげで、現在、急遽追加で調理中。ゆえに、今私がここに来ていることに関して、サクヤが気に病む必要はない」
「ああそうだな! できることなら、3分前の愚かな自分をぶん殴ってやりたいわ!」
こいつはこういう奴だって、今まで散々見てきたはずだろ、あたし!
というか、あたし、ちゃんと“コンテストの結果”はどうだったかって訊いたよなぁ!?
絶対分かってて言ってやがるだろ! あと前フリが長い!
「というわけで、これから私は
「ああとっとと行っちまいやがれこの野郎! あとその善処は、天丼になるのが目に見えてんだよ!」
あっという間にドアを開けて走り去ってしまったトウコに、あたしの台詞が聞こえたかどうかは、定かではない。
……って、トウコ今、こちらで「も」、って言ったか?
その疑問は、すぐに解けた。
トウコと入れ違いになるようにして部屋に入ってきたタマキが、両手で持ち切れないくらいにでっかい金色のトロフィーを抱えていたからだ。
「サクヤちゃん! やったよ! わたしたち、アジア地区予選、優勝だよ!」
その言葉を聞いて、あたしは。
「……あれ? サクヤちゃん、泣いてるの?」
「え? あたしが? そんなわけ……」
指摘されて初めて、自分の頬を、つ……と流れ落ちる何かの存在に気づく。
え、嘘だろ、おい。タマキじゃあるまいし、なんであたしが泣くんだよ。
「…………」
改めて、冷静に自分の気持ちと向き合ってみて、分かった。
ごめん。やっぱ、感情が燃え尽きたとか、嘘だったわ。
「やったぜタマキ超嬉しいぃぃぃぃぃぃぃぃぃぃぃぃぃぃぃぃぃぃぃ!!」
「サクヤちゃんサクヤちゃんサクヤちゃんサクヤちゃんサクヤちゃん!!」
人目がないのをいいことに、思いっきり抱き合うあたしとタマキ。
うおぉぉぉぉぉぉ! あのH通ったのか! 自分のことながら信じられねぇぇぇぇぇぇ!!
「いやっほぉぉぉぉぉぉぉぉぉぉい! ひょほぉぉぉぉぉぉぉぉぉぉ!!」
「サクヤちゃんサクヤちゃんサクヤちゃんサクヤちゃんサクヤちゃん!!」
世界大会進出だぁぁぁぁぁぁぁぁぁぁぁ!! いぇやぁぁぁぁぁぁぁぁぁぁぁ!!
◆
10分後。
「……こほん。それで、順位表の最終結果はどうなったの?」
ひとしきり騒ぎまくった後、我に返ったあたしは、何事もなかったかのようにタマキに訊ねる。
「うん、これだよ。プリントアウトして、持ってきたんだ〜」
最終結果:
1位 【__________】 ABCDEFGHIJ 10完 ペナルティ+2014
2位 【玉兎】 ABCDEFHIJ 9完 ペナルティ+1452
3位 【若葉】 ABCDEFGIJ 9完 ペナルティ+1614
「って、はあ!? なんでカズミの野郎が2位に居んのよ!?」
あいつ、あの後で、Hを通して、その上Cまで修正したわけ!?
Cは元のコードがあるし、Hもある程度までは組めてただろうとはいえ、たった15分しか時間残ってなかったのよ!? どんだけ超人なのよ!?
つーか、あたしら、9完のままだったら負けてたじゃん!
カズミの野郎、さも負けを認めたような台詞を吐いておいて、内心では抜き返す気満々だったんじゃねーか! 相っ変わらずねじ曲がった性格してやがんなぁ!?
はぁ……。これは、若葉の3人に、感謝しないとね……。
あそこで発破をかけてもらえてなかったら、確実にカズミに負けてた……。
「あ、そうそう。他のチームのみんなから、サクヤちゃんへの伝言を預かってるんだよ〜。えっとね、たしかカズミちゃんは……」
――はは。私に勝ったと勘違いしてぺらぺらと余計なことを喋りまくっていた秋葉サクヤの天高く伸びる鼻っ柱をぽっきり折ってやったら、どんな表情が見られるのか楽しみにしてたんだけどね。残念だよ。今度こそ約束通り、君達の“チーム名”を返してもらえるよう、スタッフに取り計らっておいた。それでは、またどこかで会おう。
「ああもう本当に性格最っ悪だなあいつは!」
「で、でもね、サクヤちゃん。カズミちゃんが、わたしたちの“名前”を奪ったのって、きっと、わたしたちにもっともっと強くなって欲しかったからじゃないかなー、なんて。……あ、こ、これは、ただのわたしの想像なんだけどね!」
「……分かってるわよ、そんなこと」
「え?」
「あいつの思惑くらい、お見通しだっての。緋笠カズミが心の底から望んでいるものは、強者との胸躍る闘い、それだけよ。その感情は、多かれ少なかれ、全ての競技プログラマーが持っているものだとは思うけど、それを極端に純化した存在が、あいつ。その気持ちだけは、認めてやってもいいわ」
もっとも、認めていいのは本当にそこだけで、あいつとあたしは、たとえ天地が引っくり返ったとしても決して相容れることはないだろうがな!
「おぉ〜、さすがサクヤちゃん。……それから、ブレインネクサスの2人からは」
――バーカバーカ! 10完とか頭悪いんじゃないの?
――馬に蹴られて死んじゃえバーカ!
「子供か!!」
いや、子供だけどさ!!
なんか途中からカズミにもろ潰されてたのは認識してたけど……。まあ、来年がんばれ。
「次は、絵空トオルちゃんからだね」
――ところで、“
「知 る か ! !」
そしてなぜそれをわざわざ別室で寝ているあたしに伝えようとする!!
「えっと、最後は、若葉のカエちゃんからだよ〜」
――サクヤ先輩。ごめんなさい。先輩の言う通り、私たちは、思いあがっていたのでしょう。先輩の汚いところを目の当たりにして、自分たちの未熟さを思い知らされました。
「お、ようやくまともそうなメッセージが来たわね……」
――Hを通すため、涙と鼻水で顔をぐしゃぐしゃにして机にへばりつきながら、鬼気迫る表情で二本の腕を奇怪な軌道で振り回し、白目を剥いて首をがくがくと揺らしながら闘うその姿は、率直に言って正視に耐えないものでした。
「え、ちょ、何。<
「………………」
「黙って目を逸らされたーーーーっ!」
「サクヤちゃん。……世の中には、知らない方が幸せなことって、あると思うよ?」
「いやーーっ! その優しさが痛い! そして怖い!」
――それでも、私たちは目を背けませんでした。サクヤ先輩が見せてくれると言った“汚いもの”を、一つ残らず瞳に焼き付けようと、病的に蠢く名状しがたき異形の物体から、決して目を逸らしませんでした。
「やめて! むしろ逸らして! 汚いものって、そういうクトゥルフ的なことじゃないから! もっとこう、比喩的な何かだから!」
――それで、私たちは悟りました。私たちの決意なんて、あんなの、覚悟の内にも入らなかったんだ、って。女であることを冒涜するような真似をしてまで1つの問題にしがみ付く、Acceptedに懸けるサクヤ先輩の悲壮な決意が余すことなく伝わってきて、正直、泣きそうになりました。
「泣かないで! お願いだから目を閉じて! あたしもまだ女を捨てたくないーーーっ!」
――私たちでは、まだまだサクヤ先輩の境地に至ることはできない。そう痛感させられました。そんな私たちが、先輩に対して、余計なお世話でしかない出過ぎた配慮をしてしまったことを、お許しください。今度こそ、正しい意味で言います。サクヤ先輩、申し訳ありませんでした。
「や、まあ、一番言いたかったことは伝わってるみたいだけどさ……」
――P.S. あの後【若葉】の3人で話しあったのですが、やっぱり先輩のあれを真似するのだけはちょっと…………。なので、私たちは私たちなりの道を進んでみることにします。それでは、また。
「……ねえタマキ。今日の大会で、あたしのことを慕ってくれる貴重な後輩が3人失われたような気がしてならないんだけど」
「……気のせいだと思うよっ♪」
思いっきり目を逸らされた。
◆
「ふう。厳しい闘いだった」
追加された料理を食べつくして戻ってきたらしいトウコと合流したのが、それからさらに20分後。
もちろん、トウコが持ち帰ってきたタッパーの中身については、予想通りに天丼なやり取りが行われた。
「トウコちゃん、凄かったんだよぉ。人がぎゅうぎゅうに詰まったパーティー会場の中で、まるで水の中をすいすい泳ぐみたいに動いて、目にも止まらぬ速さで次から次へと自分の皿に料理を取っていくの。それを見ていた人たちからは、“
「や、それ別に凄くないから。馬鹿にされてるだけだから」
ちなみに、あたしの攻撃を軽々かわせるほどのトウコの体さばきは、こうしたパーティの場で、できる限り多くの料理を確保するために鍛え上げられた技術らしい。本人から聞いた。奴いわく、「立食パーティーは、戦場だ」とのこと。
「サクヤに同意。あの鮮やかさはあくまで副次的に磨き上げた技術の賜物。私の本領はあくまで力強さにある。ゆえに“
「や。それも馬鹿にされてるだけだから。自己分析とかいらないから」
そもそも、あんたのそれ、
「あ、そうだサクヤちゃん。チーム名が【
「ああ、そういえばそんな話もあったわね……」
あたしたちが、チーム名なし、なんてふざけた状態でICPCに参加していられるのは、カズミが
日本国内で行われるアジア地区予選まではそれで良かったが、世界大会に出るとなれば、さすがに
「おぉ〜。やっとノーネームじゃなくなって、元の名前に戻れるんだねぇ〜」
タマキの言うことはもっともだ。
カズミから “チーム名”を返還された以上、すぐにでも昔の名前で再登録するのが自然な行為だろう。
でも、あたしには少し、思うところがあった。
「ねえ、聞いてくれる? あたしにちょっと考えがあるんだけど」
タマキとトウコに向かって、言う。
「昔の名前に戻すのもいいけどさ、あたし実は、この【
いくらカズミによって無理やり押し付けられた、チーム名とも言えないような、名前の搾りかすだったとしても。
1年間ずっと付き合い続けていれば、それなりに愛着も湧く。
「それにさ。【__________】って、あたしたちが初めて世界大会に進出した記念すべきチーム名……っていうのも変だけど、まあ、呼び名なわけじゃない。だったら、縁起もいいし、いっそのことこのまま突き進んでみない? って提案なんだけど……どう?」
冷静に考えてみれば、無茶苦茶なことを言っている気が、しなくもない。
単に、カズミに対して皮肉が言いたいだけだと受け取られてもおかしくない。
しかし、あたしのこの提案は、意外なことに2人にも好評だった。
「いいねぇサクヤちゃん! それで行ってみようよ!」
「タマキに同意」
とはいえ、本当に“名無し”のままでは、世界大会への登録ができない。
そこで、ちょっとだけ屁理屈をこねる。
「そもそも、今のあたしたちのチーム名が【__________】になってるのって、ジャッジ側の処理の都合なのよね」
名前がないのだから、本来ならばあたしたちのチーム名は、空文字列で【】とでもなっていなければならない。
でも、それだと多くのチーム名を機械的に処理するときに、色々な問題が生じる。そこで便宜的に、空白のように見える文字列をチーム名として定義しておこうという事情があって、あたしたちのチーム名は【__________】になっているのだ。
これをそのまま、正式なチーム名として登録してしまおう、というわけだ。
「そっかぁ〜。でも、読みは? これも“ノーネーム”のまま?」
確かに、そういう手もある。
空文字列では名前を呼ぶときに不便だからと、便宜的につけられた呼び名が“ノーネーム”なのだから、同様にこれを正式なチームの呼び名として登録してしまえばいいのだ。
でも、ちょっとそれでは味気ない。
なので、最後にちょっぴり捻る。
「あたしの
【若葉】の急浮上に巻き込まれて溺れかけ、カズミの巻き返しにも気づきすらしなかった。
「だから、もう一度足元をしっかり見直そうっていう、戒めのつもりで、ね。たとえどんなに実績のある強豪チームだって、コンテストが始まった直後のスタートラインはみんな0完。
そしてあたしは、頭に思い描いたチーム名を、口にした。
(了)
(※) この記事は、@highjelliesによって、Competitive Programming Advent Calendarの25日目用に書かれたものです。
(※) 我々@highjellies, @iwiwi, @omeometoの3人は、今年の11月に、チーム【__________】としてICPC2011アジア地区予選に参加し、優勝してきました。その記念に参戦記を書こうと思ったのですが、ここで、「@iwiwiの目には、今回のICPCはどのように映っていたのだろう?」という疑問が生じました。
(※) UTPC2011の問題文によると、どうやら@iwiwiには、周りの競技プログラマーがみな美少女に見えているらしいのです。そこで、「@iwiwiの主観フィルターを通して見たICPCとは、このようなものなのではないか」という想像をもとに描かれた参戦記が、この記事です。このような理由のため、客観的事実とは異なる描写が一部含まれていますが、ご了承ください。
(※) 本記事中に登場したC問題とG問題のコーナーケースは、実際に【__________】が本番中にAcceptedしたコードを撃墜することができます。
__________の ICPCアジア地区予選2011参戦記 No.2/3
1:54経過 【__________ 】 ABF 3/10完
「ちっ。
ぐしゃぐしゃと髪をかき回す。
くそっ。カズミの奴は、もうABCFGの5完だってのに……。
とはいえ、ここで焦っても仕方ない。
絶対にバグを出さないなんて、一部の人外を除けば普通のプログラマーにはまず不可能。
肝心なのは、バグを出してしまったときに、いかに速やかに対処するかだ。
このままパソコンを使ってデバッグする手もあるが、サンプルは通っていてWAの原因が推定できていない以上、ここはいったん手を引くのが最善だろう。
それに、うちのチームには、こんなときのための秘密兵器がいるわけだしね。
「トウコ。いつものやつ、任せたわよ」
「いぇっさー」
バグの入ったD問題のソースコードを印刷して、トウコに渡す。
普通なら、この紙をじっと睨んで隠れたバグを探すのかと思うでしょうけど、そうじゃない。
トウコは、無表情な瞳で、じっとプログラムを見つめていたかと思うと、唐突に、
ぴりぴり、と。
紙の上端を細長く切り取るように指で破り、そして、
ぱくり、と。
食べた。
……うん。何を言っているのかわからねーと思うから、今から説明する。
トウコは、ソースコードが印刷された紙を、(比喩ではなく)「食べる」ことで、バグの有無や種類を判別することができる。
ちなみにこれは、強豪プログラマーの多くが持っている“
ぶっちゃけあたしも、こいつがこんなことをできる理由も原理もまるで理解しちゃいないんだけど、とにかくトウコには、そういう得体の知らない“力”がある(本人に訊いても、「……気合と経験?」などと首を傾げてやがったので、たぶん自分でも分かってない)。
無論、原理なんて分からずとも、できる以上は存分に利用させてもらう。
あたしたちがリスク覚悟で完全分業体制を実行に移せているのは、もしバグを出したとしてもトウコがいるという安心感によるところが大きい。
「んぐ。のどごし爽快。バグはない」
紙の上に印刷されたソースコードを、数行ずつまとめて手で破ってから、むしゃむしゃ食べる。
これが、バグのある箇所だと、喉に詰まる感じがするらしい。
また、「のどごし」の違いで、そのバグが
この説明も光景も何もかもシュールなのだが、もう慣れた。
「もぐもぐ。うまい。バグなし」
本人いわく、コードの食べ心地の見極めは繊細な作業らしいので、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するかもしれない微妙なラインだ。
とはいえ、日本の
だとすれば、実装が楽で、早く書ける後者の解法を選ぶべきではなかったのか。
タマキは、こう言いたいのだろう。
もちろんあたしも、そんなことは分かっている。
それでも前者の解法を選んだ理由は、用意されたテストケースが万が一強かった場合を恐れた、というのも無くはないんだけれど――――。
「<
「????」
タマキの頭の中に、疑問符がいっぱい浮かんでいるだろうことが、目で見ても分かる。
ごめんね。今は説明できないの。あんた、人に物事を隠すのとか苦手そうだし。
「詳しくは後で教えてあげるわ。さ、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になってくれなければ困る。
ちなみに、送ったソースコードが確実に意図した挙動をしてくれることは、トウコの“食道デバッグ”で念入りに確認済みだ。
「? そんなことして、何かいいことあるの?」
「直接的にはないわ。けど、
意外と知られていないことだが、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、始動」
もちろんこれは、貴重な時間を使ってでも予め用意しておいたものだ。
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を得ることはできず(結局は、判明したテストケースに対する正しい答えを自力で求めなければいけない)、やりすぎるとジャッジのサーバーに過剰な負荷をかける攻撃の一種と見なされて何らかの処分を受けることもあるため、サブミット解析は、あまり真っ当な手法だとは思われていない。
とはいえ、それにも例外がある。
その例外こそが、「テストケースの入力データに誤りがないか軽くチェックするのに使う」である。
例えば、n≦50という制約のある問題で、もしnが51以上であればTLEになるコードを送信して様子を見る、といったように。
ジャッジ側の助けになるサブミット解析というのも、存在するのだ。
そして今回、あたしたちは、それを行った“ことにする”。
「Clar、送信っと」
あたしはジャッジに、Clarification、つまり質問メッセージを送る(Clar自体は、ICPCのルールで正式に認められている行為だ)。
内容は、こうだ。
あたしたち、ノーネームの提出したCとGのプログラムが、何度やっても通りません。
そこで簡単なサブミット解析を行ったところ、そちらの用意したテストケースに誤りが存在する可能性が高いことが判明しました。
なので、改めてテストケースを詳しく調査し、もし誤りが発見されたら、正しい入力に差し替えてもらうことは可能でしょうか?
と、まあ、こんな感じのメッセージを、普段使わないような丁寧な言葉で簡潔に書いて送っておいた(もちろんこれも、予め用意しておいたものだ)。
「テストケースを変えてもらうのが目的、なの? でも、これだけじゃ……」
不安そうな目でこちらを見つめてくるタマキに言葉を返す前に、ジャッジからの返信メッセージが届いた。
お。思っていたより反応が早いわね。優秀優秀。
――――申し訳ありませんが、その希望に答えることはできません。
「やっぱり……。そんな簡単に、ジャッジの人たちは動いてくれないよ……」
がっかりして声を落とすタマキに、あたしは言う。
「いいのよ、これで」
「え?」
「そもそも、コンテストも残り30分を切ったこの段階で、今からテストケースの検証や、ましてや新しいテストケースを作って差し替えなんて、出来るわけないでしょ。だから、断られて当然」
具体的に、どこがどう間違っているっていう指摘もないしね。
だから、さっきのClarは、いわば軽いジャブのようなもの。
本命は、次だ。
「行くわよ、
――――そうですか、分かりました。残念です。
――――しかし、私たちには、どうしてもジャッジの用意したテストケースに間違いがあるように思えてならないのです。
――――そこで、せめて次のお願いを聞いていただけないでしょうか?
「サクヤちゃん、これって……」
「そ。これが本題。このお願いが通るかどうかが、この作戦の肝よ」
最初のClarに対して返ってきた、素っ気ない否定の返事。
だが、あれを書いたのは、まぎれもない人間だ。
テストケースにミスがあることが発覚すれば、それはテストケースを作成したジャッジ側の責任問題。
内心では、本当に自分たちの作ったテストケースが間違っているのではないかと、ヒヤヒヤしているに違いない。というか、そうでなくては困る。
「それなりに名が知られたあたしたちのチームが、あれだけしつこく間違ってます間違ってますって訴えてるんだもん。不安になって当然だわ」
日本のジャッジの中には、あたしと個人的に知り合いな人も何人かいる。
もちろんそれで直接的な便宜を図ってもらえるなんてことはありえないが、今は動揺させることだけが目的なのだから、コネクションがあるというその事実だけで十分だ。
信用のある相手からの度重なる揺さぶりに、トドメのドア・イン・ザ・フェイス。
これで落ちなければ、嘘だろう。
「サクヤ。返信」
トウコに言われ、ジャッジから送られてきたメッセージを読む。
――――分かりました。それでは、今から5分後に、チーム【
「よしっ! 通った!」
思わずガッツポーズ。これで、か細い道が繋がった。
オペレーション
すでに提出されたコードに対して、もう一度ジャッジシステムを走らせる“リジャッジ”。
普通は何か不具合が見つかって修正されたときなどに行われるそれを、あたしたちはジャッジに頼み込んで無理やり実行してもらった。
テストケースを調査しろだの何だと言っていたあたしたちから、急に、ただリジャッジを行ってくれれば他には何もいらないという旨のメッセージが届く。
何も条件を変えずにリジャッジを行ったところで、コンテストの進行に影響を及ぼすとは思えない。それに、リジャッジするだけなら、大した手間もかからない。
そうであるからこそ、ジャッジは、厄介なクレーマーであるあたしたちを引き下がらせるために、この条件だけは呑んでくれると思ってたわ。
そしてもちろん、あたしたちには、このリジャッジを利用するための策がある。
「さあ、タマキ。あんたの
「うん! 了解だよサクヤちゃん!」
タマキは、いつも髪につけているダイス型のボンボン――というか、ボンボンのように見えるダイスを、2つ取り外して両手に握りしめる。
目を閉じて、集中。
そして、スキルの発動を、宣言する。
「<
タマキの手から、ふわりと放られた2つのダイス。
一切の回転運動なしに飛んでいった賽は、まるで定められた位置に吸い寄せられるように落下していき、机の上で、音を立てずに止まった。
出た目は、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(または
最後に、タマキとあたしが、トウコの作った撃墜ケースを含めて、どんな入力が来ても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問題について、全チームの提出コードのリジャッジが行われ、その結果に応じて順位が再計算された、とある。
――……なるほど、そういうことか。
――何? どういうことか分かったの? 言ってみなさいな。あたしが採点してあげるから。
――君達は、何かしらの
――何らかのが多すぎるけど、ま、おおむね会ってるわ。60点てとこね。ちなみに、テストデータを入れ替えたのは、あんたにはまだ見せたことのない、タマキのスキルよ。
――無論だとも。
――あんたに速度で勝てないんなら、完数で勝てばいい。そのためには、緋笠カズミ、あんたの完数を減らすのが一番手っ取り早い。簡単な理屈でしょ?
――まさか、ICPCで撃墜なんて真似をしてくるとはね。その発想力には、素直に感服するよ。自分のコードがChallenge Succeededされるなんて、TopCoderでも久しく味わったことのない経験だからね。
――ちっ、これだから赤白は。……ま、さっき、あんたが本気で驚いた顔を見れたからよしとするわ。写真に撮れなかったのが残念だけど。
――……それにしても、一つ気になることがある。
――何? まあおおよそ予想はついてるけど、訊いてごらんなさい? 今のあたしは機嫌がいいから、大抵のことは教えてあげるわよ。
――テストケースを修正し、リジャッジを誘導したこと。そこまではいい。……だが、君達は、なぜ私のコードを撃墜できるという確信を持てた? それとも、そんな確証はなく、とにかく賭けに出てただ偶然勝っただけだとでも言うのかい?
――確証? もちろんあったわよ。運否天賦も嫌いじゃないけど、勝つべくして勝つ方が、あたしの好みなの。覚えてる? あたしが主催した、プログラミングコンテスト。
――UTPC、か。
――そ。誰かさんが圧倒的大差で1位になった挙句、あたしに向かって「君と競い合えなかったのは残念だな。また今度、コンテストの参加者という立場同士で闘いたいね」なんて腐れた台詞を吐いた輩がいた、あのコンテストよ。
――……なかなか手厳しいね。
――あたしがあれを主催した目的は、緋笠カズミ、あんたについて、いくつかの事柄を確認することだった。具体的には、コーディングの癖と、それから、<
――まさか……!
――そ。そのまさか。あんたの<解法解放>は、与えられた問題に対する正しい解法を与えてくれる
――……確かに、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%の賭けに勝った挑戦者に、素直に称賛の拍手を送りたいと思う。
「あら? アイチちゃん、その顔は、何か大事なことを勘違いしているわねぇ?」
「……? 勘違い、ですか?」
「もしかして、もうコンテストは終わった、なんて考えてるんじゃないかしら?」
「……ええ。だって、もう事実上の決着はついたでしょう。ブレインネクサスは緋笠カズミの<
そう言ってから、気づく。
「まさか、トオルさん。今からコンテストに参加する気なんですか?」
絵空トオルは、多くの競技プログラマーから、畏怖と敬意を込めて、そう呼ばれている。
全世界の競技プログラマーの頂点に立つ彼女に色が無い理由は、既存のレーティングシステムでは彼女の実力を測れないからだとか、そもそもTopCoderを管理しているのが絵空トオル本人であるからだとか、様々な噂が絶えない(トオル本人はそのあたりの事情について語りたがらないため、アイチにも真相は謎)。
そんな彼女であれば、たとえ残り時間があと10分を下回りそうな今この瞬間からコンテストに参戦したとしても、ぶっちぎりで1位を取れるだろう。
彼女の
「そんなことはしないわよぉ。だって、お姉さんが1位になっても、面白くも何ともないもの」
自分が1位になれることは一切否定せずに、とろけるような声で言う。
「お姉さん言ったでしょ? サクヤちゃんたちノーネームが優勝できる確率は、五分五分だ、って」
「? ですから、その五分五分の賭けにノーネームが勝ったから、今」
「違うわよぉ。残りの五分の方は、カズミちゃんじゃなくてぇ」
トオルが言い終わる前に、アイチは、順位表に現れた、とある変化に気づく。
先ほどの風船が割れた爆音の嵐に比べれば、実に静かな、ある変化。
しかし、その一見さりげない変化は、コンテストの流れを、激変させる。
まるで、今までの全ては、しょせん予定調和だったとでも言うかのように。
「これは……、一体……!」
「だからぁ」
当然、その変化も予想していたとばかりに、絵空トオルは口を開く。
「サクヤちゃんがカズミちゃんにやったのと同じことを、今度はノーネームがやられちゃったのよぉ」
(No.3/3につづく)
__________の ICPCアジア地区予選2011参戦記 No.1/3
福岡大会 1日目
生きることは、勝ち続けること。
それは、あたし――
「うわぁ! ねえ見てサクヤちゃん、博多名物“おきゅうと”だって!」
ショートボブのくせっ毛がふりふり揺れて、底抜けに明るい声が飛んでくる。
「すごいよねえ、さすが福岡だねえ。……あれ、でも“おきゅうと”って何だろ? 民間療法?」
いつものように頭の悪いその発言に、あたしは呆れながらも答えを返す。
「それはお
「おおー! さすがサクペディアちゃん! 博識だねえ!」
「誰がオンライン百科事典よ、誰が」
何も考えていないように見えて、事実何も考えてないこの女の子――
「あうっ!」
「馬鹿なこと言ってないで、行くわよ。あたしたちが何のために博多まで来たのか、忘れたの?」
「うぅ……。ごめんねぇ、サクヤちゃん……」
タマキは、少し涙目になって、潤んだ瞳でこちらを上目づかいに見つめてくる。
おいこら、なんでこの程度で泣くんだよ。
「……ったく。初めて九州に来てはしゃぎたくなる気持ちは分かるけど、羽目を外すのは全てが終わってからにしなさいよね。もし何かあったら取り返しがつかないでしょ。……とくに、その、あんたの身に」
「! サクヤちゃん……!」
途端にぱあっと顔を輝かせるタマキ。えへーと笑いながら、にやけた顔であたしの服の裾をつまんでくる。
「んふーふーん♪ ふふんふふーん♪」
「…………」
今度は鼻歌まで歌いだした。よほど上機嫌なのか、軽くスキップまでしている。
放っておけばどこまでもついて来そうな小柄なタマキの姿を見て、あたしは――――犬みたいだなぁ、と思った。
「さっくやちゃん♪ 大好きさっくやちゃーん♪」
「ごめん。やっぱ鬱陶しいわ」
ぺちん。あうっ。
おでこを抑えてうずくまる、悩みなんて欠片もなさそうなタマキに冷たい視線を向けながら、あたしは再びため息をついた。
はぁ。せめて、“もう一人”の方も、タマキと同じくらい扱いやすければねぇ。
「タマキは相変わらず現状認識が甘い。なぜなら、ここはもう戦場なのだから」
――そう、思ったそばから。
「浮ついた態度でいれば、いつか必ずしっぺ返しをくらうことになる。常に神経を研ぎ澄ませ、持てる集中力を総動員して、周囲に細心の注意を払うべき」
背後から聞こえてきた声に、あたしはこめかみを抑えながら振り返る。
そこに居たのは――まあ予想通りなんだけど――ぴりりとした雰囲気を身に纏った黒髪の少女、
「私達は、何のためにここまで来たのか。その当初の目的を、優先順位を、決して間違えてはいけない。見知らぬ土地で道を見失えば、待っているのは破滅のみ」
「……で? 大層な御託を並べているあんたがその両手に抱えている物は、一体何かしら?」
トウコは、大量に抱えた紙袋の中から“ソレ”を一つ取り出すと、袋を破ってひょいと口に放り込んだ。
「福岡名物、“博多通りもん”。超うまい。いちおし」
「あんたが一番羽目を外してんでしょうがあっ!」
昔、空手で鍛えた上段回し蹴りを、相手のこめかみ狙いで思いっきり叩きこむ。
あたしの蹴りが直撃する瞬間、トウコの身体が少しだけ沈みこんだ。
「ちいっ! 外したか!」
技が眼前に迫っても眉一つ動かさず、必要最小限の動きだけでかわされた、だと……。
しかも、大量の紙袋(おそらく全部食料品)を抱えたまま。くそ、腹立つ……!
「私は誰よりも真剣。この博多駅に立ち並ぶ数多の土産店の中から、何処を選び、何を買い、何時食べるか。その繊細な判断は、常に冷静でなくてはとても務まらない」
言いながら、また1つ、通りもんの袋を破って口に入れる。
無表情な顔で、口だけをむぐむぐ動かしながら、トウコは続けた。
「現に、サクヤとタマキは、つい先ほど大きなミスを1つ犯している。危なかった。もし私が指摘していなければ、取り返しのつかないことになる所だった」
「は? 何よ、あたしのミスって」
自慢じゃないが、あたしがこういう旅行なんかを仕切ってミスをしたことは一度もない。
完璧主義者を名乗るつもりはないが、根が几帳面なのだ。
忘れ物や、財布を落とすなんてイージーミスは絶対にやらない自信がある。もちろん、そういうことをやらかしそうなタマキの財布をあらかじめ預かっておくことも忘れていない。
トウコは、あたしの言葉を聞いているのかいないのか、とある売店――さっきタマキが騒いでいた店だ――に向かって、すたすたと歩いていく。
「少しでも興味を持ったら、即買い。これは基本中の基本。……店員さん、おきゅうと3つ下さい」
「心っ底どうでもいいわっ!」
全速ダッシュからの
ていうか、なんで振り返りもせずに背後からの攻撃をかわせるのよ……っ!
「タマキ。少しでも興味を持った商品を買わないのは、作り手に失礼」
唖然とするタマキの手の中に、おきゅうとの入った袋が1つ。
「サクヤ。伝聞知識だけで地元名物の何たるかを語るのは、食べ物に失礼」
いまだ憤然とするあたしにも、おきゅうとが1つ。
「全身全霊で、作り手と食材に感謝を込めて」
どこからか紙皿と割り箸を取り出したトウコは、自分の分のおきゅうとを皿の上に置き、これまた何処かから出したポン酢をかけて、ぱくり。
「ってえ! 今食うんかい!」
「……予想よりうまい。これは、あと3つ追加購入も辞さない」
辞さないじゃねえよ。あと、そもそも土産品は現地で食うもんじゃねえよ。
◆
渡部タマキ。
体型は小柄。髪型はくせっ毛のある栗色のショートボブで、いつもつけているダイス型のボンボンがよく似合っている。顔はくりくりっとした丸い目が特徴的で、小動物系とでも言うのか、まあ可愛いと言えないこともない。
性格は、とにかく真っ直ぐ。感情表現が素直だと言えば聞こえはいいが、思ったことがすぐ顔に出る裏表のないタマキの姿を見ていると、この子将来絶対詐欺とかにあいそうだよなぁ、と思う。しかも本人が騙されたことに気づかないから何度でも騙されるタイプ。
吉田トウコ。
タマキとは逆に、滅多に無表情を崩さないため、何を考えているのか判然としない。目はとろんと半開きだが、以前本人から聞いたところによると、別に眠いわけではないらしい。
食べ物全般にかける熱意は、ぶっちゃけあたしが軽く引くレベル。いつ見ても何かしら食べてる。なのにスタイルは悪くない。正直むかつく。
タマキが空気を読めない子なら、トウコは絶望的なまでに空気を読まない。以前、男子に「トウコちゃんは天然だなあ」なんて言われているのを目撃したことがあるけど、あたしに言わせりゃ、トウコのあれは確信犯だ。絶対分かったうえでやってやがる。
誠に遺憾ながら、この2人の馬鹿こそが、あたし、秋葉サクヤをリーダーとする競技プログラミングのチーム、【__________】の、構成メンバーだったりするのである。
「……それで? あたしたちが東京からわざわざ博多くんだりまでやってきた目的は?」
おずおずと挙がる手が、1つ。
「はい、タマキ」
「ええと……。わたしたち3人は、ICPCの国内予選を突破したから、次のアジア地区予選に出るために、今年の開催地である福岡に……」
「はいOK。じゃあ次。あたしたちのチームの、この福岡大会での目標は?」
しゅぴっと挙がる手が、1つ。
「はい、トウコ。あと人の質問に答えるときくらいはいい加減通りもんを食うのを止めろ」
「んぐ。ラジャー。この大会に是が非でも優勝して、
「はいOK。よく出来ました」
言うと、あたしはゆっくりと息を吐きながら、2人を見回す。
そして、たっぷりと言葉をためてから、叫んだ。
「だったらなんで、あたしたち【__________】は、初っ端から
ちなみに今現在、あたし以外の2人、タマキとトウコの姿勢はといえば、正座である。
コンクリートの床に、ガチ正座。そんな2人を、あたしが冷ややかな視線で上から見下ろしている。
他のチームが本番環境のチェックを行っている中で、集合時間に遅れたあたしたち【__________】だけが、会場の廊下に締め出し。セキュリティチェックの都合上、いかなる理由があろうとも途中入場は不可能らしい。
何が悪かったのかといえば、これはもう、100%あたし以外の2人が悪い。
お昼になって、(あれだけ土産品を食べていたはずの!)トウコが「お腹すいた」と発言。その提案を受けて、あたしたちは近くにあった博多ラーメン店へと入った。
そこでトウコが迷わず【30分以内に全部食べたらタダ! ウルトラ特盛ジャンボラーメン!】を注文。慌てて止めようとするも時すでに遅し。10人前はあるんじゃないかっていう巨大なラーメンの山が、トウコの前に運ばれてきた。
で、その巨山ラーメンを、トウコはなんとわずか5分足らずで速攻完食。その上、あろうことか替え玉の注文まで始めやがった。
「30分以内に食べたものが全てタダになるのなら、私はここで倍プッシュ」などと意味不明なことをぬかしながら、残り25分フルに使って合計30杯の替え玉を完食。ジャンボラーメン(2800円)+替え玉(100円)×30=5800円分の食費を浮かせやがった。
店を出るときにちらりと見えた、店員さんの苦々しい表情を、あたしは一生忘れないだろう。
加えて、ただでさえトウコがフードファイトしていたせいで時間がおしてるっていうのに、博多駅中央街を歩いている途中で突然タマキが「ねえねえサクヤちゃんサクヤちゃん! あそこに東急ハンズがあるんだけど行ってもいいかな行ってもいいよねせっかく博多まで来たんだもんねもしも博多店でしか買えないゲームがあったりなんかしたら行かないと一生後悔するもんねそれじゃ行ってくるから後よろしく!!」などと(タマキは数理パズルだのボードゲームだのに目がない)一瞬でまくしたてるやいなや目にも止まらぬ速さで走っていってしまったため、さしものあたしも止める暇がなかった。
慌てて追いかけるも、店内を爆速で動き回るタマキを捕獲するのにかなりの時間を要し、結局「セブンワンダーズを2つ買ったら14人で遊べるようになったりしないかなあ〜」などと博多店一切関係ない戯言をほざいて商品棚を眺めていたタマキを強制的に引きずって退店させたころには、これまた30分以上が経過してしまっていた。
いくら入念な下調べを欠かさず、時間に十分な余裕を持って行動するのがモットーのあたしと言えども、ここまでの
めでたく、あたしたちのチームは集合時間に5分遅刻し(それでも! それでも5分遅れに抑えたのだ! あたしは!)、今こうして、廊下に締め出しをくらっている次第である。
「……で、2人とも、何かあたしに言うことは?」
ゴミを見るような絶対零度の視線を向けるあたしに、タマキは耐え切れなくなったのか、土下座して詫びる。
「ごめんなさぁいサクヤちゃん! ハンズがわたしを呼んでいたから、つい……つい、我慢できなくて! うわあああああん!」
うむ。まあ、いつまでも怒っていても仕方ないし、反省してるなら許してやるか。
あと、無生物の声が聞こえるとか、アニメの中以外で言ったらただのイタい子だからな?
「で、トウコも何か言うことは?」
「ラーメン10人前を5分で食べられたのなら、理論上25分で替え玉50杯は行けたはず。……無念。私もまだ未熟」
「ようしてめぇだけは一発殴らせろ歯ぁ喰いしばれ!」
反省するポイントはそこじゃねぇよ!
「おや。また何やらお馬鹿なことをしている3人組がいるようだな」
平坦だが通りのよい、涼しい声が響いた。
「……ちっ。お前か」
真っ直ぐ伸びる赤みがかった茶髪。整った顔立ちながら、その両目には、生半可な人間なら一睨みで萎縮させてしまえるであろう力強さが潜んでいる。
「はは。お前とはまた冷淡だな。偉大な
「あたしに何か用。
精一杯のうざったさを込めて言ってやるが、この女――
「別に用向きがなければ話しかけてはいけないなどということはあるまい。ただの情報収集の一環とでも思ってくれたまえ」
「前回大会の優勝者サマが、あたしたちから有用な情報を得られるとはとても思えませんけど」
そう。緋笠カズミの率いるチーム、
周囲に超人的な実力を見せつけ、大差で1位の座を奪い取っていった、緋笠カズミと玉兎。
無論、あたしたち3人も、その闘いで無残に敗れ去ったチームの1つだ。
そのときの、あたしたちの最終順位は、2位。でも、1位の玉兎との差は、歴然としていた。
ラスト10分で重量級の構文解析問題を通さなければ負けという絶望的な状況にまで追い詰められて、そのまま成す術なく敗北。カズミさえいなければなんて、言い訳にもなりやしない。
加えて、その闘いで、あたしたちのチームは、“名前”を、失った。
「私としても、優勝するのは自分のチーム以外にありえないなどと傲慢なことを考えているわけではないのだよ。そして、もしも我ら玉兎を上回るチームが現れるとしたら、その最有力候補は君達、【__________】だろうとも思っている」
「あたしらを“名無し”にした本人が、よくもぬけぬけと」
「おや。しかし正統な勝負をして負けたのは君達だろう?」
「……ちっ」
去年のICPC。あたしたちとカズミは、チームの“名前”を賭けて闘った。
この賭けを提案したのはカズミの方だ。もちろん、そんな賭けを馬鹿正直に受けてやるメリットなんて何もありやしない。だが、あろうことかカズミは、
なかば強制的に執行された賭けゲームの結果は、ご存じの通り。
あたしたちのチームは、今まで慣れ親しんだ名前を失い、【
これ以上ないってくらいの、屈辱と共に。
「ああ。もちろんこの大会で君達が私達を制した暁には、きちんと名前を返してあげるとも。安心もらって構わないよ」
「ふん。当たり前でしょ。あたしたちが何のために闘ってきたと思ってんのよ」
カズミは、あり得ないくらいむかつく女で、あたしとは天地がひっくり返っても決して相容れない自信があるけれど、勝負に関してだけは公平な奴だ。約束はきっちり守るだろう。
だとすれば、あたしのやることは簡単だ。ただ、目の前のこいつを完膚無きまでに叩き潰せばいい。
いけすかない女の鼻っ柱を、へし折ってやるわ。
「ねえ見てヒロト。
なんて、カズミといがみ合っている間に、また一人。
――いや、一人というべきか、二人というべきか。
「ああ、
「用がなければ」「話しかけちゃいけないの?」
「はは。それはもっともだ。君達、
「うん。だってボクたちは最強で」「そして最速だからね」
「おやおや。頼もしいことだ。今年もいい勝負ができることを期待しているよ」
「カズミお姉さんもね」「でも、今年はボクらが優勝だよ」
今カズミと話しているこいつらは、
双子というだけあって、顔も声も服装も、何から何までそっくりで、この2人を見た目で区別するのは不可能に近い。
「うん、今年のボクたちは誰にも負けない。もちろん」「サクヤお姉さんにだってね」
「何それ。あたしを煽ってるつもり?」
「ふふっ」「それはどうかな?」
ったく。安っぽい挑発だこと。
こんなガキっぽい奴等の言葉に惑わされてペースを乱す奴がいるなら、この目で見てみたいわ。
「むー! 負けないもん! 優勝するのは、わたしとサクヤちゃんとトウコちゃんのチームなんだから!」
――前言撤回。同レベルのガキには効果覿面でした。
「あれれ? タマキさんとトウコさん」「どうして床に正座してるの?」
「あー……。これはまあ、何というか、ちょっと一言では言えないような深い理由があってね……」
「はしゃぎすぎて
「一言で言うなっ!」
この……! トウコの奴、チームの恥部を堂々と……っ!
「ふうん。それは可哀想だね」「レモン飴いる?」
「いただく」
「もらうなっ!」
なんかもう台無しだよ! プライドとか色んなものがな!
「その代わりと言ってはなんだけど」「この大会中、ボクたちのチームに協力してくれない?」
「む……。しかし、それは……」
「レモン飴」「5袋追加で」
「裏切りも辞さない」
「500円程度の菓子で買収されてんじゃねぇ!」
というかこの双子、なんでトウコの扱いを熟知してるんだよ!
「だったら私からもいいかな。東京に帰ったら、今度、満漢全席のフルコースを御馳走しようじゃないか。もちろん料金は私持ちで」
「カズミ様。一生ついていきます」
「てめぇは小学校の道徳の時間からやり直せーっ!」
他人から物をもらってもついて行ってはいけませんって習っただろうが!
「あらあら。みんな、同じ日本代表チームの候補なんだから、仲良くしなくちゃダメよぉ」
甘ったるい声が、ふんわりとこの場に響き渡った。
「おや。貴方は」
「
「はぁ。また面倒な奴が一人」
「む? お姉さんに向かってそんな口のきき方は良くないぞ? サクヤちゃん、めっ」
「……はいはい。すみませんでした」
チーム【
ゴージャスな金髪を縦ロールに巻いた、典型的なお嬢様スタイルながら、キツい所は一切ない。むしろ、過剰なまでに人当たりが良い。
タマキとは別の意味でふわふわしたお方で、あまり人間界の常識に頓着していないご様子。一人称はまさかの「お姉さん」。
そんな良く言えば天然、悪く言えば非常識なお嬢様ではあるが、彼女が現れた瞬間、場の雰囲気が一変したのは誰もが認める所だろう。
なぜなら彼女こそが、日本の競技プログラミング界の頂点に立つ、いや、世界中で最も優れた競技プログラマーとして名高い、絵空トオルその人なのだから。
「光栄ですね。貴方ほどの人物が、わざわざアジア地区予選に足を運んでくださるなんて」
「だってぇ。みんなが頑張っているのなら、それを間近で見ていたいじゃない?」
緋笠カズミが“超人”ならば、絵空トオルの強さは“人外”。
世界全土を見渡しても彼女に比肩する人間はいないほどの逸材。望めば
その理由は、彼女ならまあ、一つしかないんだろうなぁ……。
「トオルお姉さん……!」「お姉さんは、今日の大会……!」
「ん? ああ、安心していいわよぉ。みんなの邪魔なんてしないわ。お姉さんは、今日のコンテストで、1問たりともAcceptを出すつもりはないから」
「!」「!」
……これだ。
この人は、強者の余裕なのか何なのか、自分が大会で勝利することに一切関心を持っていない。
彼女が大会に参加する理由は、最も間近でみんなの姿を見ていられるから。
彼女は、ただ他の競技プログラマーが頑張っている姿を眺めていればそれだけで満足だという、筋金入りの変態さんなのだ。
「貴方と本気で競い合いたいという気持ちも、なくはないのですがね」
「ふふ。それは止めておいた方がいいわよぉ。お姉さんの圧勝すぎて面白くないから」
自慢でも挑発でもなく、これをナチュラルに言えるお人なのである。察して欲しい。
格上の相手への挑戦が大好きなあたしでも、正直、トオルに勝てるビジョンが一切見えない。彼女だけは、別格、なのだ。
「……行くよ、ヒトロ」「行こう、ナオト」
「双子ちゃんも、明日は頑張ってねぇ〜」
ひらひらと無邪気に手を振りながら、去っていく高橋兄弟を見送るトオル。
酔狂ここに極まれり、といった感じだが、おそらく彼女は、本気で全員のことを応援しているだけで、一切の他意はないのだろう。
「さ、あたしたちもそろそろ行くわよ。プラクティスに出られなかった分、今日は早く寝て、体調だけでも万全にしとかなきゃね」
「了解だよサクヤちゃん!」
「ラジャー。ところで晩御飯はどこで」
「うるさい黙れ!」
立ち去るあたしたちと、不敵に笑う緋笠カズミの視線が、重なる。
――それでは、また明日。去年と同じ、つまらない結末にならないことを祈っているよ。
――心配してくれなくても結構。あんたは、二度と立ち直れないほどに負かしてやるわ。
交差は一瞬。それでも、伝えたいことを伝えるには十分だった。
そして、決戦の日が、訪れる。
福岡大会 2日目
「うわぁ……。人がいっぱいだねぇ、サクヤちゃん!」
「あんた、これでアジア地区予選に出るの何度目よ……」
体育館1つ分くらいの広さはあるコンテスト会場に、とうとうあたしたちはやってきた。
「さ、2人とも。
全国各地で行われた国内予選を突破し、このアジア地区予選に駒を進めた日本のチームは、全部で28チーム。その中には、この業界では少なからず名の知られた競技プログラマーの姿もちらほら見うけられる。
とはいえ、そのほとんどの実力は、正直言ってあたし1人の足元にも及ばない。
油断でも慢心でもなく、あたしたちとの優勝争いに絡んでこられるレベルの強豪チームは、数えるほどしかいないと見ていいだろう。
無論、最優先で警戒すべき相手は、チーム【玉兎】――緋笠カズミだ。彼女のプログラミングスキルは、(トオルを除けば)全参加者の中でも群を抜いている。
去年のようにカズミに負けることがあれば、たとえ2位だろうと何だろうと、その瞬間に
「……だったら、何とかしてやろうじゃないの。必ずね」
チームの名前も、優勝の栄冠も、全部まとめて取り戻す。
そんなことを呟きつつ、周囲を見回す。
すると、近くの机(カンニング防止のため、隣の机でも数メートルは離れている)に、見知った顔がいるのを見つけた。
「あれ? あんたたち、チーム【
あたしたちの後ろ斜め後方の机に座ってパソコンをいじっている、大人しそうな女の子3人。
彼女たちのチーム、【
「あ……。サクヤ先輩。お久しぶりです」
「よっ、カエ。“先輩”はいらないって、いつも言ってるでしょ」
「す、すみません。けど、サクヤ先輩には色々と恩がありますので……」
2年前のICPC国内予選。競技プログラミング初心者で、右も左も分からず困っていた彼女たちに偶然出会ったあたしたちが、参加登録やら何やら色々と手を焼いてあげたのが、チーム若葉との出会いだった。
そんなことがあって以来、若葉の子たちは、あたしたちのことを先輩と呼んで慕ってくれている。
過去のICPCの成績はまあ中の下程度で、3人とも今日に至るまでいまだに
少なくとも、あの性格がねじ曲がったカズミの野郎なんかよりも、100倍マシだ。
「ま、いっか。つもる話は後にしましょ。今は目の前の勝負に全力を尽くさないとね」
「はい! 先輩たちの胸を借りるつもりで頑張ります!」
「リラックスリラックス。そんなに緊張してると、解ける問題も解けないわよ」
そんなことを言いながら、カエの肩を叩く。
さて……と。あたしもここらで気合い入れないとね。
ノーネームの机に戻ってみると、そこには溢れんばかりのお菓子の山が。
「……トウコ。これは何?」
「お菓子。山盛り」
「うん、知ってる。どこから持ってきた?」
ずびしぃ! と部屋後方を示すトウコの指。
そこには、ICPC参加者がコンテスト中に食べるために、スタッフが用意したお菓子入りの大きな箱が……無い。
「もしかして、箱ごと全部?」
「うん」
「持ってきた?」
「いえす」
「返してこい」
「でも」
「何だ?」
「私がここで全てのお菓子を食べ尽くせば、他の参加者は飢えて競技に集中できない。大勝利」
「か・え・し・て・こ・い!!」
◆
箱全体を参加チーム数で割ったくらいの量のお菓子を残し、他すべてを元あった場所に戻して帰ってきたトウコは、露骨にがっかりした顔をしていた。
「……サクヤの、いけず」
「うっさい喋るな食欲馬鹿」
あたしは、淡々とパソコン周りのセットアップを進める。
それと同時に、必要な道具をリュックから取り出して机の上に整然と並べていく。
計算用紙、筆記用具、英和辞書、主要なアルゴリズムと定番のコードを網羅した紙ライブラリ。
方眼用紙は、通常のものだけでなく、正六角形を敷き詰めたバージョンもきちんと用意。
とにかく多種多様なダイスが詰め込まれたタッパー(タマキの趣味)、片手に収まるサイズの小型折り紙100枚セット(タマキの趣味)、それと、残ったお菓子……の空き袋(既にトウコが全部食った)。
準備は万端。あとは勝つべくして勝つのみ。
静かに闘志を燃やしつつ、深呼吸。
……よし。コンディションはバッチリだ。改めて、周囲の気になるチームを見回す。
にこにこと笑みを絶やさない、チーム【世界一】、絵空トオル。
相変わらず手を繋いで2人べったりの、チーム【ブレインネクサス】、高橋ナオト&ヒロト。
自然体ながらも隠せない威圧感を放っている、チーム【玉兎】、緋笠カズミ。
今日、あたしたちは、この戦場で、頂点に立つ。
「全力で行くわよ! タマキ! トウコ!」
慣れ親しんだ意識が、身体の奥底に沈みこむ。
日常モードから、非日常の闘いへ。
コンテスト用に最適化された感覚。心地よい緊張感が、あたしの身体の中を満たしていく。
生きることは、勝ち続けること。
さあ、始めよう。
この1年間、ずっと死んでいたあたしが、再び蘇るための闘いを。
「The Contest is Start!!!」
審判のアナウンスと共に、これから5時間にも及ぶ長い闘いの幕が切って落とされた。
0:00経過 【__________ 】 0/10完
ICPCのアジア地区予選では、5時間で10問の問題を解き、その成績をチームごとに競い合う。
ルールは単純で、完答した問題数――完数が多いほど、順位が高くなる。
また、問題を解くたびに、それまでに経過した時間がペナルティタイムとして分単位で加算されていき、同じ完数のチーム同士であれば、このペナルティタイムが少ない方が高順位となる。
加えて、ペナルティタイムが加算されるときには、その問題に間違った回答を送信した回数×20分のペナルティタイムが上乗せされる。
つまり。
より早く、より正確に、より多くの問題を解く。
やるべきことは、皆同じ。たったそれだけの、シンプルな目的。
にも関わらず、それがプログラミングコンテストである以上、そこには様々な戦略が生まれうる。
「タマキはA問題、トウコはB問題! 任せたわよ!」
「了解だよっ!」「がってん」
ICPCでは、3人1組のチームが、協力して問題を解く。
とはいえ、メンバーが3人いたとしても、1人のときの3倍の問題数が解けるようにはならない。
2倍にするのも絶望的だ。下手をすると、1人でやるのと何ら効率が変わらないなんてことにもなりかねない。
その最大の原因は、競技中、各チームごとにパソコンが1台しか与えられないことにある。
コーディングを始めとして、テスト、デバッグ、そしてサブミットと、何をするにしても必要不可欠な計算機が、たったの1台。
いくらチームに3人いようと、並列に動けないのなら宝の持ち腐れだ。パソコンの台数という厄介な制約のせいで、チーム全体としての効率が大きく制限される。
1+1+1は、決して3にはならない。
だからせめて、あたしたちは、その計算結果が1.5くらいにはなるように最善を尽くす。
「A解けた! それじゃ、パソコン借りるねっ!」
「ラジャー。サクヤは?」
「そうね……。この"FUKUOKAYAMAGUCHI"って文字列とサンプル入出力から察するに、おそらくFはただのShortest Superstring。これなら、わりとすぐに書ける」
「把握。私は引き続き、Bのコードの構想を固める」
3人のメンバーによる、完全分業体制。
これが、長らく闘いを積み重ねていく中で確立された、あたしたちの闘い方だ。
普通、こういったチーム戦では、ペアプログラミングと呼ばれる手法が好んでとられる。
1人がコードを書き、もう1人がミスを指摘する。2人のプログラマが、1台のパソコンを使って開発を進めていく、ペアプログラミング。
ペナルティタイムの加算のされ方を考えると、ICPCでは、序盤に簡単な問題をスピーディーかつ正確に通すことが重要だ。だから、コーディングとデバッグを同時に行えるペアプログラミングとの相性がいい、と言われている。
しかしそれは、コーダーの書いたコードにバグがあることを前提とした考え方だ。
もしもコーダーが1つのバグも出さずに最後までコードを書きあげれば、その間ずっと画面を注視していた2人目がやっていたことは、完全な徒労になる。
加えて、リアルタイムデバッグのために、コーダーの実装方針をわざわざ口に出して2人目に伝える手間なんかを考えると、1人のときよりコーディング速度は落ちてしまうのは必然だ。
だからこそ、1人1人が責任を持って、自分が担当した問題のコードを最初から最後まで書きあげる。
もちろん、助けを請われれば協力はするが、基本的には各自の裁量に任せてノータッチ。
そしていざ自分にパソコンが与えられたら、極力手を止めずに最後まで走り抜く。
多少のリスクは覚悟してでも、常時最大のパフォーマンスを発揮し続ける。
そのくらいのことができなければ、カズミに勝って優勝するなんて、夢のまた夢だ。
「よぉしっ! A組めた! サンプルも通った! 行っくよー! サブミット!」
さあ、ファーストサブミットの結果は。
「やったぁ!
「タマキ偉い。次は私の番」
問題に正解したことを示す風船が、ノーネームの机の上にあがる。A問題の風船の色は、赤だ。
それを確認するとすぐに、トウコがタマキと入れ替わり、B問題のコーディングを始める。
頭の中で実装方針を固めていたおかげで、タイピング中に不必要に手が止まることは少ない。
(よし。出だしは好調……ね)
完全分業体制は、個々のメンバーがある程度高い実力を持っていて初めて成立する戦術だ。たとえ1人に問題を任せたところで、その1問を解くのに2時間も3時間もかかっていては話にならない。それならまだ、皆で相談しながら方針を固めていった方がマシというものだ。
解法の考案、コーディング、万が一バグを出したときの速やかなフォロー。
そういった、問題を解くうえでのあらゆるステップを、全員が独力であるレベル以上に行えること。それが、分業を行ううえでの最低条件だ。
……うちのチームの、普段馬鹿ばっかりやってる2人も、そういう点に関しては、まあ、少しは信頼してやっても、いい。
だからこそ、腐れ縁が切れることなく今までやってこれたわけだし。
「それじゃ、わたしは、次に解けそうな問題探してるねー」
A問題を解き終えたタマキは、まだ誰も手をつけていない残りの問題文を読み始める。
ICPCのアジア地区予選は、国内予選までとは違って、問題文が英語で与えられる。
題意に曖昧な点が生じないよう、かなり冗長に書かれた英文を読み解く作業には、思った以上に時間がかかる。
簡単な問題から順に解いた方がペナルティタイムの合計が少なくてすむICPCにおいては、問題の難易度を見極めることが非常に重要だ。
しかし、そのためにまず10問全ての問題文を読んで解法を導き出すなんてことをやっていては、それだけで大幅に時間をくってしまい、本末転倒だ。
例年簡単な問題が配置されていることが多いAとBや(真っ先にタマキとトウコにこの2問を投げたのはこれが理由)、さっきのFのようにキーワードからぱっと問題と解法が推測できる場合はいいが、そういうケースはあまり多くない。
そこで、問題を解く順番を決めるのに役に立つのが、
会場前面のスクリーンに大きく映し出されている順位表には、どのチームが、どの問題を、何回間違え、最終的にどのくらいの時間に通したのかが、事細かく記載されている。
1つのチームが、全10問の中から簡単な問題を的確に探し当てるのは難しいとしても、それが集団になれば話は変わる。
どのチームも、何の事前情報もない段階では、ランダムにでも、とにかく何かしらの問題文を読まなければ話は進まない。そこで難しい問題に当たってしまえばそれまでだが、偶然簡単な問題を引き当てたチームは、迷わずその問題を通しに行くだろう。
1つ1つのチームは十分に賢い挙動を示すとは限らなくても、多くのサンプルが積み重なれば、各問題の難易度が浮き彫りになってくる。
つまりは、順位表を見れば、多くのチームが通している問題ほど簡単な問題であると判断できる。
アジア地区予選まで来るようなチームであれば、誰しもが理解し活用している、ICPCにおける常套戦術。
チームリーダーとして、誰にどの問題を割り振るべきかをできるだけ正確に判断しなければいけないあたしは、順位表全体に素早く目を通して、すでにどこかのチームの手によって解かれた問題をリストアップする。
「AとB……を除けば、あと解かれているのは、H問題、だけね」
コンテスト開始後15分で、HがAcceptedされている。
さっそく問題冊子をめくって、そのH問題とやらを読む。
Problem H : ASCII Expression 以下のような、2次元グリッド上に表現された数式が入力として与えられる(サイズは20×80以下)。 BNFに似たルールに従って、数式を計算した結果を2011で割った余りを出力せよ。 ............2............................2...................................... ...........3............................3....................................... ..........----.........................----..................................... ............4............................4...................................... .....2.+.------.+.1...............2.+.------.+.1................................ ............2............................2...................................... ...........2............................2........................2.............. ..........----.........................----.....................3............... ............2............................2.....................----............. ...........3............................3........................4.............. (.(.----------------.+.2.+.3.).*.----------------.+.2.).*.2.+.------.+.1.+.2.*.5 ............2............................2.......................2.............. ...........5............................5.......................2............... ..........----.........................----....................----............. ............6............................6.......................2.............. .........------.......................------....................3............... ............3............................3......................................
「これ、は……!」
いわゆる、構文解析と呼ばれるタイプの問題。しかも2次元グリッドという見慣れない形式での。
「こんなもの、一体どうやったら、たった15分で通せるわけ……?」
構文解析の問題は、やることはシンプルで紛れも少ないが、実装量はかなり多く、どうやっても多大な時間の消費は避けられないものと相場が決まっている。
だが、現に通しているチームがいる以上、Xmas Contest 2010のB問題のように、強実装に見えて実は気づけば一瞬で解ける問題、なのか……?
問題文をもういちど精読し、見落としがないかどうか確認しようとして――――唐突に閃いた。
「まさか……!」
顔を上げて、もう一度順位表を確認する。
H問題を通したチームの名は――――ブレインネクサス。
0:18経過 【ブレインネクサス】 H 1/10完
「やったねヒロト」「うん、大成功だね。ナオト」
高橋ナオトと、高橋ヒロト。
チーム【ブレインネクサス】の核たる双子の兄弟が、にっこりと笑みを交わし合う。
皆がA問題やB問題しか通していない中で、ブレインネクサスがH問題を通した。
この事実が、コンテストへと与える影響は、計り知れない。
「みんな、慌ててH問題を読み出してるよ」「必死に考えているチームもいるね」
周囲のチームの様子を観察しながら、自分たちの狙いが的中したことを悟る。
この作戦が決まれば、上位陣の戦線ですらガタガタにすることができる。
そんな未来を想像して、兄弟は無邪気に微笑んだ。
「ヤヒロちゃん、他の問題の翻訳はどう?」「残ってるのはあと6問だったよね」
ブレインネクサスの3人目である彼女のTopCoderのランクは、
だが、そんな彼女も、ブレインネクサスでは欠かせない役割を担っている。
英語で書かれた問題文の読解、そして要約。
高橋兄弟がプログラミング以外の些事に煩わされることのないよう、兄弟と問題文との間の橋渡しを行う。
それが、彼女にしかできない、ブレインネクサスにおける伊藤ヤヒロの役割だった。
「B、C、E、G、I、Jの翻訳、全て終わりました」
「さすが、優秀だね。……ナオト、この問題の中だと、Iが一番いいみたいだよ」「了解だよ、ヒロト」
ヤヒロがヒロトに渡した何枚かの紙には、彼女の几帳面さが伝わってくるような小さく整った文字で、全ての問題文の大意が簡潔かつ的確にまとめられている。
たとえプログラミングスキルが皆無であろうとも、これをコンテスト開始からわずか20分以内に行えるほどの実力を持った人間は、
コンテストの序盤に、他のチームが10問もの問題文を少しずつ読み解くのに四苦八苦している中で、自分たちだけが全ての問題文に関する完璧な情報を得られることのアドバンテージは、思いのほか大きい。
読んだだけで解法がすぐに分かる簡単な問題を、決して見逃すことがないのだから。
だが、ブレインネクサスの作戦は、この情報アドバンテージを、ただ消費するだけには留まらない。独占した情報を活かして、場の流行を操作する。
順位表を見て次に解くべき問題を決めるという方法を、誰もが理解し活用しているからこそ、それを逆に利用する。
読めばすぐに解き方が分かる問題の中から、もっとも実装が重い1題を選んで、できるだけ早くAccepted。
ブレインネクサスは、狙い通り、AとB以外で解かれている問題がHしかないという状況を作り出すことに成功した。
そうなれば当然、他のチームは、Hは15分あれば解ける程度の簡単な問題だと思い込む。皆が皆、こぞってH問題を解こうとする。
だが、H問題は強実装。1時間以内に通せるチームすら少ないであろうほどの、難問だ。
それでも、大半のチームは、自らの力だけで難問が難問であることを確信できるほどの実力を備えてはいない。
15分で通したチームが存在するという情報を盲目的に頼りにして、何かに気がつくことができれば一瞬で解けるタイプの問題だと思い込み、無駄に時間を浪費する。
さらに、その影響は、中堅チームだけに留まらない。
優勝争いに絡めるほどの上位チームなら、H問題を読めば、これが簡単な手段で通せる問題ではないことくらいすぐに見抜けるだろう。もしかすると、ブレインネクサスの企みに気づいたチームもいるかもしれない。
しかし、そうしてHを避けたとしても、彼らは次に解くべき簡単な問題を定めることができない。
多くの中堅チームがH問題に囚われて、様々な問題にアタックすることを止めてしまえば、必然、順位表は硬直する。
普段なら、中堅チームのトライ&エラーの結果を参考に、飛び石の上を渡るように悠々と簡単な問題だけを選んで解いていくはずの上位陣が、道標を失って右往左往する。
1つ1つ問題文を読んで、問題の難易度を自力で見極めていくしかない。
そうなれば、ペナルティタイムの増大は避けられない。
全チームの共有資産であるはずの順位表に、誤った情報を流して無力化する。
そして、自分たちだけが握っているヤヒロの要約を参考に、最高速度でコンテストを駆け抜ける。
それこそが、ブレインネクサスの作戦だった。
「I問題は幾何か。この問題も、すっごく大変そうだね」「でも行けるよ。ボクたちなら」
幾何の問題もまた、構文解析と並んで、実装が重くて複雑なジャンルとして知られている。
本来ならば、中盤から終盤にかけて解くべき問題。
にも関わらず、ブレインネクサスは、場にさらなる混乱を招くべく、IのAcceptedを眼前の順位表に叩きつけるために、動く。
「さあ。始めよう、ヒロト」「うん。いつでもいいよ、ナオト」
そう言い合うと、2人は、目を閉じて意識を集中させる。
彼ら兄弟に固有の
「「<
その瞬間、2人の思考は、繋がった。
(#include
かっと目を見開いたナオトの頭の中を、ものすごい速度で文字の羅列が流れていく。
それに応じるように、ヒロトは、凄まじい速度で流れるようにキーボードを打鍵する。
みるみるうちに、ディスプレイの中にI問題を解くためのソースコードが組み上がっていく。
(double a=abs(c[j]-c[i]),b=R-r[i],x=R-r[j],costheta=(a*a+b*b-x*x)/(2*a*b);\nif(costheta<-1+EPS)cnt++;\nelse if(costheta<1-EPS){\ndouble theta=acos(costheta),t1=arg(c[j]-c[i])+theta,t2=arg(c[j]-c[i])-theta;\nwhile(t1>M_PI)t1-=2*M_PI;\nwhile(t1<-M_PI)t1+=2*M_PI;\nwhile(t2>M_PI)t2-=2*M_PI;\nwhile(t2<-M_PI)t2+=2*M_PI;\nif(t1
このスキルの発動中は、脳の一部が
言葉を介さず、相手の脳に直接思考を書き込む。
自分の意思を相手に伝えるのに、これほど効果的なコミュニケーション手段もない。
やわらか頭脳を誇る高橋ナオトが、閃いた解法をコードに落としてヒロトの
全国タイピング甲子園で優勝経験のある高橋ヒロトが、書き込まれたソースコードを、恐るべき速度と正確さでそのままテキストファイルに起こす。
言うなれば、一切の無駄を排した、究極のペアプログラミング。
“最強最速の双子”と称される彼らのコーディング速度は、他の追随を許さない。
普通のプログラマーのコーディングに時間がかかるのは、思考とタイピングを交互に行っているからだ。
人間は、2つの物事を同時に実行できるようには作られていない。
思考中は、文字をタイプする手は止まり、タイピング中には、どうしても思考は止まる。
その度重なる切り替えで思考の断絶が何度も生じてしまい、余計な時間を消費する。
しかし、彼ら高橋兄弟にはそれがない。
兄のナオトは、書くことを一切気にせずに、ただ最高の効率で考え続けるだけ。
弟のヒロトは、考えることを一切せずに、ただ与えられた文字列を最高の速度で打ち込み続けるだけ。
他の誰にも真似できない、最強最速の役割分担。
Hを15分で通す、という作戦を成功させることができたのも、ブレインネクサスに高橋兄弟がいたからこそだ。他のチームでは、たとえ真似しようとしたとしても、Hを通す頃には、本当に簡単な問題があらかた判明し尽くしてしまっているのがオチだろう。
(ans+=(next-event[k].first)*(R-r[i]);\n}\n}\nif(maxcnt
ずっとディスプレイを見つめ続けていたヒロトが、ナオトに声をかける。
「……ナオト?」
しかし、いつもならばすぐに返事がくるはずの相手から、何の反応もない。
不思議に思って振り向くと、ナオトは会場前面の順位表を見つめて、唖然としていた。
「どうしたの、ナオ……っ!!」
そして、気づく。
順位表の中にある、余りに異様なその1点に。
慌てて周囲を見回し、周りのチームの様子を確認する。
だが、もはや誰一人としてH問題に取り組んでいる様子はない。
「ナオト……!」「ヒロト……!」
やられた。まさか、こんな方法で流行操作を無力化されるなんて。
<
2人は、驚きと悔しさ、そして憎しみを込めて、「それ」を実行に移したチームの名を叫んだ。
「「ノーネーム……!!」」
0:27経過 【__________ 】 A 1/10完
「うわぁー。サクヤちゃんが悪い顔してるよぉ……」
タマキがまん丸い目でこちらを見つめながら、そんな失礼なことをのたまってきやがった。
失敬な。あたしはただ、先輩への礼儀を知らない生意気なガキどもに、お灸を据えてやっただけだっての。ただし、気持ちちょっとだけキツめに。
「でも、今ので不利になったのは私たちも同じ。サクヤ、どうする」
「どうもしない。あたしたちは、Strictlyにカズミの野郎を上回ればいい。完数で勝つ、それだけよ」
「わかった、従う。それと」
「何?」
「B問題、Accepted」
「よくやったトウコっ!」
青い風船が上がる。これで2完目だ。
そこに表示されている、今のあたしたちの成績は。
【
Score:2
Penalty Time:44(+100)
A問題 Solved Time +16
B問題 Solved Time +28
H問題 ------ Time (+100)
まず、タマキが開始16分でAを解いて、1完。
続けて、コーディング方針を固めていたトウコがBを12分で通して、2完。
最後に、あたしが“最強最速の双子”をぶっ飛ばすために被った潜在的なペナルティが、+100分だ。
「あっ、サクヤちゃん! ブレインネクサスが、今度はIを通したよ!」
I問題?
ふむ……今度は幾何ね。どうせまた強実装のやるだけ問題なんでしょ。
「トウコ。懲りないガキどもに制裁。オペレーション
「いぇす、まいろーど」
トウコはI問題を開くと、ついさっき解いたばかりのB問題のソースコードを選択し、そのまま
No - Wrong Answer.
No - Wrong Answer.
No - Wrong Answer.
No - Wrong Answer.
No - Wrong Answer.
またたく間に不正解のメッセージが積み重なり、潜在的ペナルティタイムが膨れ上がる。
【
Score:2
Penalty Time:44(+200)
A問題 Solved Time +16
B問題 Solved Time +28
H問題 ------ Time (+100)
I問題 ------ Time (+100)
その瞬間、Iに挑戦しようと思っていた他のチームが、ざわつき出したのが肌で感じられた。
H問題のときと全く同じ反応だ。まあ、そりゃ戸惑いもするでしょうね。
なんせ、今まさに自分たちが挑もうとしていたI問題に、前回準優勝チームが5回も
これを額面通りに受け取れば、実力のあるチームが5WAもするような危険な問題は避けようと思う。
もしも不自然なWAラッシュに違和感を覚えたとしても、それはそれで、何か裏がありそうなよく分からない問題は後回しにしようと考える。
たとえどちらに転んだとしても、ブレインネクサスの流行操作に一石を投じることができる、という寸法だ。
もし、「Hは難問ですから皆さん手を出さない方がいいですよー!」などと大声で叫ぼうものなら、下手をしなくとも退場処分だ。
でも、これなら、ルール上何の問題もない。
なんせ、あたしたちはただ、問題に挑んでWrong Answerを出しただけなんだからね。
ブレインネクサスの机を見やると、高橋兄弟が、悔しそうにこちらを睨みつけている。
ああ、いい気味だ…………じゃなくて、これであいつらが順位表を荒らしてくることはもうなくなったと見ていいだろう。
一度この5WA戦術を実行に移して潜在的+100ペナルティをくらってしまった以上、同じことを2度やろうと3度やろうと、あたしたちに被害は少ない。どうせ同じ完数ならば勝ち目はないことに変わりはないのだから。
ゆえに、ブレインネクサスが何度同じことを繰り返してこようと、あたしたちは、そのたびに何の躊躇いもなく全く同じ返し技が使える。そして、そのことはもちろんブレインネクサス側も承知している。
だから、ブレインネクサスには、もうこれ以上不自然な順番で問題を解き続けるメリットがないのだ。いくら最強最速とはいえ、簡単な問題から解いた方が合計ペナルティが小さくなることには変わりがない。もう場を撹乱することが不可能だと分かった以上、彼らも自分たちの利益を最大化するために動くに決まっている。
これでめでたくナッシュ均衡が成立。ノーネームとブレインネクサスの、ごく個人的な闘いは終了だ。
「でも、サクヤちゃん。本当にあんなにペナルティもらっちゃって、良かったの?」
タマキが不安そうに訊ねてくる。
まあ、そう思うのも当然でしょうね。というか、別に良くはない。
「順位表が硬直して、より被害を被るのはあたしたちの方だからね」
もちろん、あたしが言ってる比較対象は、チーム玉兎のことだ。
「あんたも知ってるでしょ? 緋笠カズミの
<
緋笠カズミの持つそのスキルは、「問題を読んだ瞬間、その正しい解法が頭の中に浮かび上がってくる」という、いかにもチートくさい常時発動型の能力だ。
ゆえに、極端に実装が重いもしくは複雑な問題を除けば、カズミにとって全ての問題はほぼ等価。
たとえ順位表が使えなくなったところで、頭から順に目についた問題を解いていきでもすれば、それだけで他を圧倒するほどに小さいペナルティタイムを叩き出せるだろう。
「解法を考える」という、競技プログラマーにとって何よりも重要なステップから解放されたカズミは、高橋兄弟とは別の意味で最速。それも、終盤の難しい問題になればなるほど、他のコーダーと比べての相対的な速度は増していく。
まともにペナルティタイムで競い合っても、勝ち目は薄い。
あたしたちには、もとより完数で勝つしか選択肢がなかったからこそ、ペナルティ+100みたいな大胆な戦術に踏み切れた、というわけだ。
「だから、あたしはペナルティタイムを犠牲にしてでも、順位表を正常に戻すことを選択したってわけ。完数で勝つために、5時間という限られた時間を少しでも無駄にしたくない。簡単に解ける問題がどれか分かってるっていうのは、戦略を立てる上でも大きなアドバンテージになるからね」
「なるほどね〜。さすがサクヤちゃん、色々考えてるんだねー」
「あんたが考えなさすぎなのよ……っと。よし、できた。F問題、Acceptedよ」
「やったねサクヤちゃん! おおー、ピンクの風船だ! これで3完だよ!」
手を叩いて喜ぶタマキ。
まあ、ちゃんとFの問題文を読んでみたら、本当にただのShortest Superstring問題だったんだけどね。しかも復元もなし。こんなの、脳内にあるライブラリをただ打ち込むだけの簡単な作業だ。
高橋ヒロトほどの速度はないにしても、あたしだってタイピングはそこそこ速い。考えることがないのだから、楽勝にもほどがある。
「さっきも言った通り、あたしはこのままDを解き始めるわ。復活した順位表も参考にしつつ、あんたたち2人は次に解く問題を考えといて。任せたわよ」
「了解だよっ!」「あいあいさー」
F問題はないも同然だったので、トウコがBを解いている間、あたしは(H問題に拘泥しなくなった何チームかが解いていた)Dが簡単な問題だと判断して、解法を考えておいた。
Fほど速攻ではないにしろ、それほど時間もかからず通せるだろう。
D.cppを開く前に、もう一度、順位表の一番上に目をやる。
そこに当たり前のように居座っている怪物、すでにノーネームと1完差をつけてトップに君臨している化け物チームを率いる女王の名を、改めて胸に刻む。
――覚悟してなさいよ、緋笠カズミ。
1:05経過 【玉兎 】 ABFG 4/10完
現在の順位:
1位 【玉兎】 ABFG 4完 ペナルティ+108
2位 【__________】 ABF 3完 ペナルティ+86
3位 【ブレインネクサス】 AHI 3完 ペナルティ+93
「ふむ……。Wrong Answer覚悟での自爆戦術か。秋葉サクヤも、なかなか面白いことを考えるものだね」
C問題のソースコードを淡々と一定のリズムで打ち込みながら、緋笠カズミは呟いた。
そして、つい先ほどサクヤがタマキに説明したのと同じ思考を辿り、その突飛な作戦こそが彼女にとっては最善の選択であったとも確信する。
「いやはや、実に愉快だ。だが、それでこそ闘いがいがあると言うものか」
そう言いながらも、彼女の口調からは、自分が負けるなどとは微塵も思っていないことが伝わってくる。
「さあ、ノーネームの諸君。君達は、
アルゴリズムを考える時間が完全に“0”であるカズミは、自身の圧倒的優位を客観的に認識しつつも、しかし一切の油断を含まない声で、不敵に笑った。
それは、TopCoderのレーティングが3000以上になった人間にのみ与えられる、競技プログラマーにとっては最高位の称号の1つ。
レーティング2200以上の
「さて。C問題、Acceptedだ。次はDでも解くとするか」
コンテストを支配する女王たる存在、この場で唯一の
わずか1時間20分で、10問中5問、半分の問題を解き終えて、2位以下に2完差をつけたカズミは、ふと唐突に何かを思いついたらしく口を開く。
「ああ、そうだ。その前に、潰せるチームは潰しておかないとね」
と。
「<
本当に、何気なく呟いた。
1:27経過 【ブレインネクサス】 AHI 3/10完
「B問題、組めたよナオト!」「やったねヒロト! 早速テストだ!」
完成したコードをコンパイルして、サンプルインプットを入力として与えてやる。
その結果は。
「あ、れ……?」「なんで……?」
Segmentation fault.
そう1行だけ表示された画面を見つめ、呆然とする高橋兄弟。
慌ててソースコードを読み返して、さらに愕然する。
「何!? このプログラム」「メチャクチャだ……!」
文単位では意味が通るものの、全体として何をやりたいのかまるで判然としない。
ただ単に、コンパイルできる文をランダムに並び変えただけのような、B問題とは一切関係のないコードの羅列。
2人の目の前に現れたのは、そういう、まるで意味の分からないソースコードだった。
「ヒロト! これどういうこと!?」「ナオト! ボクにだって分からないよ!」
ナオトは、確かにB問題を解くためのコードを正確に思い浮かべた。
ヒロトも、確かに脳の
どちらかのミスで、多少のバグが混入することはあれど、ここまで意味不明なコードが出来上がるはずがない。
「ナオト! とにかくもう1回、行くよ!」「うん! ヒロト!」
「「<
“最強最速の双子”は、再び彼らの
だが、高橋兄弟のこの選択は、完全な判断ミスだった。
理解できない現象には、必ず何かしらの理由がある。
その原因を明らかにしないまま、いくら同じことを繰り返しても、結果は同じ。
それは例えるなら、Time Limit Exceededをもらったソースコードを、もしかしたら僅かな差で通るかもしれないという希望に縋って、何度も何度も提出し続けるような行為に等しかった。
1:41経過 【世界一 】 0/10完
「ふふ。双子ちゃんたち、大変ねぇ」
絵空トオルは、ふんわりとした甘い声で呟いた。
1問たりともAcceptを出さないと豪語した彼女は、その宣言通り、コンテストが始まってからずっと、他のチームの様子を観察しているだけだった。
その表情には、微笑みが絶えない。
「あの、絵空さん。高橋兄弟に、一体何が?」
そう訊ねたのは、
彼女は、トオルがまともに争うつもりがないということを理解したうえで、チーム世界一のメンバーとしてここにいる、いわばトオルの付き人のような存在だ。
「ああ、あれはねぇ。双子ちゃんが<
「? 彼らが
「ええ。双子ちゃんの
「緋笠カズミの、<結線>? 彼女の能力は、<
「あら、知らなかった? カズミちゃんは、スキルを2つ持っている、世にも珍しい競技プログラマーなのよぉ」
だが、2つの異なるスキルを同時に使いこなす人間など、聞いたこともない。
「
「普通はないわよぉ。だからこそ、カズミちゃんは特別なのねぇ」
トオルは、そんな競技プログラマーは、カズミ以外に見たことがないと言う。
そして、彼女が知らないのなら、それは本当に世界中でカズミだけなのだろう。
「カズミちゃんのもう1つの能力、<
<結線>によって作られる
だがそこに、いわゆるアクセス履歴のようなものは残らない。
第三者の手による、悪意あるデータの改竄に気づけない。
「なるほど。それで、あの兄弟はあんなに慌てているというわけですか」
「3人目の<結線>使いが現れるなんて、普通じゃ起こりえないことだから、たぶん双子ちゃんたちは、自分たちの身に何が起こっているのかさえ分かってないわねぇ。それに、もし理解できたところで、逆転は難しいでしょうねぇ」
仮に高橋兄弟が緋笠カズミの介入に気づけたとしても、それを止める手だてがないのならば何の意味もない。逆に高橋兄弟がカズミの共有領域にノイズを書き込んだとしても、それをカズミに無視されて終わりである。
そもそも、正しいプログラムを正確に伝えなければならない高橋ナオトと違って、緋笠カズミは適当なタイミングで適当なコードを共有領域に書き込んでやるだけでいい。事実、カズミはこの介入をなかば無意識的に行っており、それによってカズミ自身のコーディングに悪影響が出ることもない。
そして、最強最速の連携が断たれてしまえば、2人は並の競技プログラマー以下のパフォーマンスしか発揮することができない。加えて、3人目のメンバーである伊藤ヤヒロも、プログラマーとしては完全に戦力外だ。
「ブレインネクサスは、ここで事実上の脱落、ですか」
それにしても、とアイチは思う。
コンテストにおいては万能と言ってもいい効果を持つ、<
汎用性が高く、仮にヘウレカ以上の性能を持ったスキルの使い手が現れたとしても対応できる、コピー能力<
そして、
こんな超人めいた力を持った相手に、まともな人間が勝つ方法なんて、本当に存在するのだろうか?
しかし、目の前にいるこのお嬢様の反応を見ていると、どうやら彼女は、このコンテストが緋笠カズミの独壇場だとは思っていないようなのだ。
先ほどからトオルがしょっちゅう様子を気にしている、とあるチーム。
もしかすると、そのチームが、カズミに勝利するなんて奇跡が、起こりうるのだろうか?
そう考えて、アイチは、思ったままをトオルに告げる。
「絵空さん。あなたは……
絵空トオルは、コンテスト開始直後から、ノーネームの3人の様子を実に楽しそうに眺めていた。
もしや彼女たちは、カズミを上回るほどの特別な存在なのか。
「そうねぇ…………」
アイチの興味本位の質問に、この場で唯一カズミよりも格上の、人類最強のお嬢様は、しばし考え込むような様子を見せた後、
「五分五分、ってところかしらねぇ?」
と、答えた。
(No.2/3につづく)