大会に関してはこちらを参照。
去年の戦績に関してはこちらを参照。
四度目の挑戦。 泣いても笑ってもこれが最後だったのだが…。
去年と同じメンバーで出場した。 大会の形式も去年と大体同じだったので、その辺は安心だった。 去年と違ったのは、私は今年が最後であるというのと、 狙うのは全問正解の1位のみだということ。
5問正解の2位。 ああ、なんてこった。
帰り際に湯浅先生に「万年2位」と言われた。 確かに、去年の愛媛大会も上海交通大学に負けて2位だったし、 世界大会のパラレルチャレンジもどこか南アフリカのところに負けて2位だったし、 去年のICFPも3位で賞金を逃したり、そういうことばかりだけど、 そんなに的確に言われても…。落ち込みます。 それに、万年2位は京大自体がそうでしょ？ しゃあないやん。
今年も6問、日本語併記。 難易度はA(簡単)、B(簡単)、C(簡単)、D(難しい)、E(難しい、大変)、F(普通)、ぐらいだろうと思う。 AとCは何の前提もなしに簡単。 Bも簡単だけど、AとCよりはコード量が要るかも知れない。 Fも解き方は簡単。とくに悩んでしまうことはないだろう。 コード量がABCより大分必要だろう。 DとEはABCFとは別次元の難しさ。 Dは解法を思いつくのが大変か。解き方が分かれば グラフに長けている人ならあっさり解けるだろう。 Eは一番時間がかかるだろう。最後にEを解けるだけの時間が残せるかがポイントだ。
提出したコード一覧。 すべて実用的な時間で正解を出力することを確認している。
コードサイズなど。
$ wc *.cpp 39 59 558 a.cpp 75 119 1195 b.cpp 57 99 883 c.cpp 84 144 1906 d.cpp 141 248 2815 e.cpp (書きかけ) 96 154 1977 f.cpp 492 823 9334 total
おまけ。一分おきに収集した成績表。 成績、3分おきにしか更新されてないような気もするけど。
大学のネットワーク障害で当日の9時までメール機能が復旧しなくて、 参加が危ぶまれる中、練習セッションが始まった。 メールは何とか使えるようになったものの、 それ以前に送られたメールが受信できていないので、 サブミットの仕方とかが分からない。 仕方がないので、大会本部に再送のお願いを出して、問題だけさっさと全部解いておく。 全部解いてもまだメールが来ないので、模擬練習会の記憶を頼りに サブジェクトを適当に書いて送ったらなんだかアクセプトされてしまった。
そういうわけでさくっと3問通して、最後の問題である。 とりあえず去年の秘密の数である「5963」で送ってみたが駄目だった。 まぁ、当たり前というかなんと言うか。 駄目だったので、去年と同じく文面自動生成プログラムを作って 頑張って送ろうか、と思っていると、横のほうにいたechizenチームが 「M問題解けましたよ」と言って颯爽と立ち去っていった。 スコアを見ると10回ほどしか間違った形跡がない。 というか、5回ぐらいしか間違ってなさそうなチームもある。 何でーーーーー？？？？？どっかに答えのヒントが書いてあるの？ 模擬練習会のときと同じく前の問題に答えが入っているのかとか、 問題文のソースにこっそり書いてあるのかとか、色々考えてみたけど 全然駄目。とりあえずいつもどおり順番に送ってみることに。 そうこうしているうちにもどんどん4問正解のチームが増えてくる。 もう、何で自分たちだけ分からないのかあせるあせる。 20回ほど送ったところでアクセプトが来た。 それを見るとどうやら1980ぐらいから2050ぐらいの間に答えがあるようだ。 それと、こんなに多くのチームが解いていることからして･･･2005か？ とりあえず、範囲とデータ2から解を絞り込んでみる。 あれ？答えが一つに絞り込めない？ まぁ、きっと答えは2005だろうということで、それで送る。 見事にアクセプトされた。 しかしまぁ、年号とは何とまぁ安直な。 これはあてずっぽうでも解けるで…。正直ショックだった。
というわけで、なかなか幸先の悪いスタートであったが本番である。 もう、緊張すること緊張すること。 絶対全問解くのだ。そのためには10-20-20-30-50-50(分)ぐらいのペースで解くぞ、と意気込む。 そんな中、ついに国内予選スタート。
いつもどおりまずはA問題である。 問題が長くてびっくり。 なかなか意味を把握できずにいると、 M氏がほかのに行く？とか言って来たが、 Aが難しい訳がないので拒否する。 読み終わると、要するに単利と複利を計算すればいいということが分かったので さっさとコーディング。 途中、なぜか資金をdoubleで計算しようとしていて 何箇所か書き換えをしたが、 とりあえず開始15分ぐらいでアクセプト。
問題を読み進めていたM氏に次に渡されたのは問題C。 Bは？と聞くとBは図形だし、こっちのほうが簡単そうだと言うことだ。 内容を聞いてみると、確かに簡単だ。 ローマ数字みたいな表記を足し算する問題。 パーズの必要もないし、例外もほとんどない。 さっさと実装。さっさとアクセプト。 開始30分ほどでアクセプト。 これAより簡単じゃないの？
与えられた図形が回転移動で一致するかどうか判定する問題。 回転と逆順8通りについてノーマライズして単純に比較すればいいだろう。 これもさっさと実装。アクセプト。 開始45分ぐらい。
DとEが難しいようなので、Fを解くことに。 ロボットが床の汚れを全部拭くときに、 必要な移動回数の最小値を求める問題。 床の汚れが10個しかないので、全探索すれば終了。 汚れ間の距離は幅優先で簡単にもとまる。 これもさっくりと実装。コードがやや長くなったが、 なんとノーミスで通過。 開始75分ぐらい。 ここまではきわめて調子が良かった。
次、問題Eとどちらをするかであるが、 問題Dのほうが解法が分かれば短時間で書けそうだった。 問題Dは速さの違う馬車を使って目的地まで行くときに 最短時間を求めよと言う問題。 で、問題Fを解くまでにM氏が考えてくれたには、 馬券を使う順番を固定して、 その8!通りについてダイクストラすれば出来そうだということだった。 そういうことで、じゃあ書いてみるかと言うことになった。 しかし、よく考えてみると、馬券を固定してダイクストラってどうやるんだ？ ある位置に到達するまでに使う馬券の枚数って固定じゃないやろ？ というわけで、よく分からなくなってしまった。 結局ほかの方法を考えようと言うことになった。 私が考慮に沈んでいる間にM氏が問題Eを書き始めることに。
問題Eは折れ線運動をするロボット達が互いに通信可能範囲に入ったときに 通信を行うとして、最終的にあるロボットが持っていたデータを どのロボットにまで伝播できるかを求める問題。 かなり幾何問題なようだが、ABCFをといている間に M氏が式を導出してくれたようなので、 それを打ち込んでもらう。
問題Dの解き方を必死に考える。 ルートが決まると、時間を最小にする馬券の使い方は 一通りに決まるので(長いほうから大きな数を割り当てていけばよい) ルートを全探索すればいけるかな、とも考えたが、 全ルート候補は (30*29/2) C 8 もあるので、おそらく無理っぽかった。 うんうんと考えること15分。突然いけそうな方法をひらめく。 馬券の使用状況に応じて各ノードを(2^8)倍すれば、 あとはそれをダイクストラすればいけそうだ。 計算量は、ノードが7000個ぐらい、エッジが14万本ぐらいになるが、 O(V log E) のダイクストラなら大丈夫そうだ。 そうと分かれば問題Eから代わってもらう。 グラフを作るコードとダイクストラをゴリゴリと実装。 が、ここで問題が発生。ダイクストラの書き方を良く覚えていなかった。 はっきり言ってグラフは苦手分野だが、 弱点を補強していなかったのは全く駄目だったと言える。 兎にも角にも、世界大会に持ち込んだ資料に書いてある ダイクストラの手順を見ながら頑張ってダイクストラを実装する。 大分かかってようやく完成。 何箇所かバグが出たが、これも大分かかって修正。 ようやくサンプルが通ったので、 入力を入れる。…二つ目までは出たが、三つめがいくら待っても出ない。 もうちょっとかかるのかな、と言うことで再び問題Eにバトンタッチ。 この時点で残り50分ぐらい。
また頑張って書いてもらう。 その間に私は問題Dの実行が終わるのを待ちつつ、 実装が正しいかどうかを検証する。 10分ぐらい経過した。一向に終わりそうな気配はない。 と、ここで、駄目そうなところが見つかる。 ダイクストラの未確定頂点を何を考えたかmultimapで持っていたのだが (mapだとキーの重複が許されないし、priority_queueはなんかめんどくさそうだと思ったからだろう) デバッグ時に見ていた限りでは、キー、値両方の重複がいっぱいあったようだった。 これじゃオーダがちゃんとならないかも知れんなぁ、ということで ここをsetを使うようにしたらいけるんじゃないかと気づく。
そういうわけで、multimapをsetに変えたところ (multimapとsetはかなり似ているので、コード修正はほんのちょっとだった) 一瞬で答えが出るようになってしまった。 はっきり言ってショックである。 このまま回答送信、アクセプト。 残り時間20分強。
問題Dであほみたいに時間を食ってしまったので、 残り20分ぐらいになってしまったが、問題Eを頑張ってもらう。 コードが100行ぐらいになったときに、あとどれぐらいかと聞いたら まだ3分の1ぐらいだと言うことだった。 そんなにかかるんか？と思いつつ、これは無理かも知れんなぁと思い始める。 残り10分。まだ出来そうにない。 3分、2分、1分、終了。 駄目だった。
今年も終わるまでスコアボードは一回も見なかった。 で、終了後、恐る恐る見てみる。 GNC------。全問解いてるやん。 GNCと言えば東大の中でも実力はトップクラスだと思われながらも なんだかいつも本調子が出ていないように思われるチームである。 今回はちゃんと実力が出せたんですね。おめでとう。 で、うちのチームはと言うと2位だった。 4問目ぐらいまでは最速だろうなぁと思っていたので それもあって5問正解の中でトップを取れた形か。
はっきり言って全問解けなかったのは悔しい。 終わってからあとどれぐらいで出来そうかとM氏に聞いてみるとあと20分ぐらいだと言うことだ。 こうやって後から見直してみると何が悪かったのかは明白である。 問題Dに時間をかけすぎだ。 結局問題Dに手を付け始めてからアクセプトまで80分もかかっている計算になるが、 アルゴリズムを考え付くまでが15分ぐらい、遅いのを待ったり高速化したりのために20分ぐらいかかっている。 正直、グラフが得意な人ならこの80分の半分もかからないだろう。 ABCFまでが非常にうまく行っただけに残念だ。 全問解いたGNCにしても、問題Eに一時間ほど費やしているわけで、 やっぱりDがこの体たらくでは駄目である。
というわけで、今回はこういう結果に終わってしまったが、 この借りは11月の東京決戦で必ず返す！！！ 待ってろ、東京。