大会に関してはこちらを参照
国内予選に関してはこちらを参照
ほげほげ。
年齢制限により今年が最後のチャンス。 国内予選の実績から海外派遣をしてもらえることになったものの、 一位のチームがマニラを希望した都合上 世界有数の激戦区、北京へと送り込まれる結果に。 のしかかる重圧を撥ね退け、おそらく最大にして最後のチャンス、 東京大会に全てを賭ける。
どうやら今年も勝ちました。 テキサスにいけるようです。
全体のRankは二位、オープン参加を除いた公式の順位では一位だった。 今年は最初からFirst Placeの賞状、商品がもらえた。 本当にうれしかった。
今年は本当に大変だった。 明らかに今年の日本チームは去年よりもはるかに実力の底上げがなされていた。 それは参加者全体にも言えるし(今年はついに国内予選突破最低ラインが三問を越えた)、 上位陣にも言える。 上位陣のレベルが上がったと感じる根拠はいくつかある。 ACM-ICPC OB/OGの会(OGっているんかいな…？) による模擬練習会・強化合宿が今年も行われたこと。 GNC(東京大学のチーム)が東大、東工大などのチームを集めて隔週で練習会を開いていたこと。 特に後者は回数も多かったので非常に強い影響を及ぼしたように思う。 練習会が開催される以上、こちらも参加しないとライバルチームが実力を伸ばすのを指をくわえて見ていることになってしまうので、 私たちも参加することは必然だった。 最初の方こそ成績にそれなりにばらつきがあったが、 夏ごろから全体の成績に差が全然付かなくなってきた。 みんな超強化されてしまった。 去年世界に行けたこともあって、うちのチームはほかのチームよりも一歩抜きん出ていたと 思っていたのだが、これで完全に差はなくなってしまったと感じた。 大会一月ほど前、GNC練習会はほかのチームも出ているのだ、 周りと同じことしかしていないのなら、このままでは勝てない、と危機感を覚え、 チームだけで週2回ほど集まって練習することにした。 それでも思うように練習は進まず、結局、焦燥感の塊を抱えたまま東京大会を迎えてしまった。 しかし、GNCはこのような練習会を開いたら自分たちも大変になると分かっているのに それをあえてやるということに頭が下がる。 自信があったのか、それとも中国にやられっぱなしな日本の現状を憂いたのか。
国内チームだけでも大変なのにアジア諸国からも刺客がやってくる。 今年は中国から4チームも来る。GNCいわく、香港も意外と強い、 台湾も意外と強い、で、それらも打ち倒さねばならなければならない。 GNCの人と事前に分析した結果、上海交通大学は間違い無く最強、 ていうか世界最強、んなもん勝てるか、というレベル。 復旦大学は中国国内の予選を見る限りでは かなり強い。強いけど、ここに勝たないと東京大会から日本チームが選出されないということにもなりかねない。 日本のチームが2チーム以上復旦大学に勝てるとは思えないので、 復旦大学に勝てばおそらく日本一だとは思われる。 国立台湾大学も強いはずだけど、ここに負けているようでは話にならない。 北京大学は来るのが一番手じゃないから問題なかろう、という分析。 (恐ろしいことにほとんど当たっていた) ただ、GNCの人はオープン参加の概念を分析し間違えていて、 すでに台北で勝っている上海交通大学がノーマル参加になると思っていたみたいだ。 だから、その分事前の分析よりははるかに勝ちやすい形となった。
戦略は去年と全く同じ。 完全分業、完全シリアル型(つまりバグっても、バグが取れるまで次に行かない) eXtream Programing。 一番コードを書くスピードの速い私がコードを書いて、K氏がそれを補佐(プリ計算などもやってもらう)。 そして圧倒的英語力を誇るM氏が英語をすべて読み、読め次第アルゴリズムの考察に入る。 理想は私とK氏がコードを書いている間にM氏が問題を解読し、さらに次の問題の解法を見つけてくれるような形だ。 長時間バグが取れなくなったり、次の解くべき問題がなくなってしまったら 大変な時間のロスだが、日本のアジア地区大会レベルの問題だとそういうことはあんまり無い。
あと、今回は直前に行った模擬練習会で多大なる反省点が見つかったので、それも踏まえる。 日本の問題は一番難しい(というか厄介な？)問題はいつも幾何と決まっているので、 解くべき問題がなくなったからといって安易に幾何に走らない、 幾何を解き始める前にほかのチームが解いている問題の解法を考える。 幾何はほかのチームが解いたか、明らかに明確なアルゴリズムが分かったときにのみ 手を出してよい。 二年前の会津では幾何に手を出して壮大に失敗、先日の練習会でも幾何で大幅に時間をロスしたので、 やはり、安易に手を出すなというのは絶対だ。
今年も予想通り9問で5時間。 難易度は、 A(非常に易しい)、 B(多少面倒)、 C(易しい)、 D(面倒)、 E(やや易しい)、 F(普通)、 G(やや難しい)、 H(難しい)、 I(非常に厄介) ぐらいだろうか(基準がバラバラで申し訳ない)。 A〜Gまでは普通に解ける問題だ。あとはここをいかに確実に解くか。 時間が余ったらHかIに手をつけることになるが、 とりあえずHをお勧めしておく。 Hは時間がたくさんあれば解けるようだ(Nimrod談)。 Iはいやらしいデータがいくらでも作れそうなので、 安易に手を出すべきではない。
当日作ったソースはまだ届いていないので、届いたら公開します。 アドホックさが大変素敵なソースです。
とりあえず、タイムテーブルを。
あまり無駄が無くてかなり理想的だが、 いろいろ失敗はあるので、 コーディング速度が今と同じでも あと40分ぐらいは詰める余地がある。
時刻 問題 返答 10 A - Prime Yes 38 C - Cube Yes 67 E - Mobile No, Wrong Answer 80 E - Mobile Yes 111 B - Library Yes 138 F - Race Yes 210 G - Network Yes 246 D - Train Yes 299 H - Bingo No, Wrong Answer
当時の様子を詳細に書いてみます。
前日に会場入り。 一番乗りでRegistrationを済ませる。 席は幸運なことに一番後ろの中央付近。 ここからなら楽に全席を見渡せる。 東京大学GNC、IHI、while1fork、qooの席を確認。 上海交通大学Nimrodが三つ前の席にいることを発見。 その前に復旦大学Powderysnowがいるのも発見。 隣に東工大、斜め前に京大チームもみつけた。 試合中にどの辺を見ておけばよさそうかは大体頭に入った。
そして当日。大体三十分前に席にスタンバイ。 とてつもない緊張感に襲われる。 それに伴いおなかが痛くなる。 決戦直前にトイレに行かなかったことって無いかもしれない…。 それはともかく…、待ち続ける。 とにかく落ち着いて、落ち着いて集中するんだ。 瞑想を繰り返す。前の席にPSPで遊んでいる人がいた。 うーん、余裕だな。 しかし、あと五時間後には勝者が決まっているのか。 もっとも、到底そんなところはイメージできなかったのだけど。
カウントダウンとともに戦いの火蓋は切って落とされた。 直前に何度も何度も開始直後に行うことをイメージしていた。
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream cin(".txt");
return 0;
}
去年のとちょっとだけ変更 これはつつがなく終了。 この時点で三分ぐらい。
それからすぐにA問題を教えてもらう。 A問題は、与えられた数(<10000)が何通りの連続する素数の和で表されるか。 うむうむ確かに簡単だな。 素数を生成して二重ループの探索で終了か。 数が10000までというのが気になるが、 素数の密度は結構低いし、GCC4の最適化はすごいので、 何とかなるだろうなと思って実装に取り掛かる。 (このとき実装しているアルゴリズムはO(n^2)だと思っていたが、 後で検証したところ、求める数を越えた時点でループをカットしているので、 数列の和の下限をいい加減に見積もってもオーダはO(n^1.5)だということが判明した。 さらに、帰りの新幹線の中で線形アルゴリズムも思いついた。 本番でAを解いたチームのどれぐらいが線形アルゴリズムを用いたのかは分からないが、 まぁ、どっちにしてもたいしてコード量は変わらないだろう。 ちなみに線形アルゴリズムは、一言で言うと、しゃくとりメソッド。 値の上限が100万とかなら、こちらを使わざるを得ないだろう) 実装は5分ぐらいで完了。 サンプルサンプル〜、というところで、サンプルのありかが分からないことに気づいた。 昨日の練習時と同じ場所とも思われたがその紙を持ってくるのを忘れた。 どうするか…と悩んでいるととりあえずM氏がクラリフィケーションを出してくれることに。 結局A問題の入力は手で入力してサブミットした。 結構速く行けたかな？と思ったのだが、なんとRunIDは4。正直ショックだ。 トップは同じ京大のechizenチームだったようだ。次いでNimrod、どこか、うち、だろうか。 しかし落ち込んでいる暇は無い。Yesが返って来たので即座に次の問題へ。
次は問題Cを与えられた。 問題は、側面をいろいろな色で塗られたさいころがいくつか(<=4個)与えられたとき、 最小いくつの面を塗り替えれば回転を許してすべてのさいころが同一になるか？というもの。 さいころが4つしかないので、24^4とおりをすべて試せばよい。 さいころはちょっぴり苦手だが、とりあえず回転はテーブルを24通り手書きしてやることに。 K氏にテーブルの作成をお願いして、私はテーブルができたものとしてコーディング開始。 途中、クラリフィケーションを送る。 クラリフィケーションの回答は「スタッフに聞け」だった。 責任をたらいまわしされてるだけのような気がしてきた。 M氏がスタッフとコンタクト。…ぜんぜん話が通じていない。 彼の英語力からするとスタッフの方に問題があったと思われるが、 かなり長いこと食い下がった結果、サンプルインプットのありかを教えてもらうことができた。 そして、コーディング。 コーディングが終わるころにはテーブルもできていた。 頑張ってそれを打ち込む。打ち込み終わってみてからよく確認してみると、 私の意図していた順番とK氏の作ったテーブルの順番が違う。 これはやっちゃったか？と思ったが、4個目と5個目を入れ替えると正しくなることが 分かったので、修正、実行。 さいころが4個のとき答えが合わない。4と書くところを3にしたままだった。 (コピーしまくった結果…) さくっと直して送信。Yesが返ってきた。
これを解いている途中、Nimrodがすでに二問目を上げていた。 やはりすごいな、と思いつつもNimrodが解いた問題に取り掛かることに。 問題E、いくつかの重りが与えられるので、それを長さ1の棒の両端に取り付けて モビールを作る。ひとつに纏め上げたときに出来上がるモビールの最大サイズを求めるという問題。 重りの数は6個まで。そういうわけなので、全探索ができそう。 (探索数はトーナメントの方法*各棒の向き = 6C2*5C2*4C2*3C2*2C2*2^6 なので余裕) 具体的な処理は、各ノードを重り+左右の出っ張りと考えると楽そうだ、 というM氏の意見を元にそのように実装することにした。 探索手順は、重りのセットの中から任意の二つを引っこ抜き、マージし、 それを突っ込んで、そのセットで再帰、みたいなことをやったのだが、 それを実現するためにvectorではなくlistを使いたくなった。 とはいえ、私はこういう問題でlistを使ったことが無い。 insert、eraseの返す値とか、以前にとったイテレータが有効かとか。 まぁ、何はともあれ、持ってきていたSTLのマニュアルを見ながら実装。 かなり手間取った末に完成。しかし、むちゃくちゃ怪しい…。 サンプルに対しては正しい答えが出た。 不安ながらもSubmit。しばし待つ。回答は非情にもWrong Answer。 どこが間違っているんだ。
K氏と二人でコードを眺める。 やはりlistの使い方が怪しそう、 なんだか死んだiteratorを使うケースがあるような感じだ。 やっぱりコンテスト本番でなれないことをするもんじゃない。 vectorで実装する方法を考え、探索コードをすべて書き直し。 書いてみるとlistよりも速く書けた(実行速度は多分遅くなったけど)。 やっぱりなれないことはしてはいけない。 アルゴリズムは同じなのでどきどきだが、再度問題Eをサブミット。 緊張して待つ。Yesが返ってきた。ということはやはりlistの使い方がまずかったか。 この時点で三問正解はかなりトップっぽかった。 Nimrodはすでに三問解いていたような気がするけど、 まずまずの滑り出しといったところか。
次はB問題をやることに。 Eを解いている間に会津大学のClaxが解いていた問題だ。 あんまり時間をかけた様子が無いので、大して手間のかかる問題ではないと予測。 とりあえず説明を受ける。 説明がややこしい。理解するまでにしばしを要した。 図書館に何人かが本を何冊か返しに来る。一定規則にしたがって 動作する図書館司書の動きをシミュレートして、 全リクエストを処理するコストを計算せよ、という問題。 さて、実装をどうするかな、といったときに K氏がリクエストはzipしてしまえば単に一列になることを発見。 さらに私が本のアクセス時刻は棚ごとに持たなくてもいいことを発見。 かなり実装を簡略化できることが分かった。 そのままごしごしと実装。 15分ぐらいで完成。 サンプルが通らない。 シミュレーションステップを出力してみる。 答えが合わない。 ルールが一箇所抜けていたので、そこを修正。 ちゃんと動いた。Submit、返答はYes。
次は問題F。 この問題がこの時点でほかのチームが解いていてうちが解いていない唯一の問題になっていた。 問題Fは、タイヤ交換のみがスピードに影響を与えるレーシングにおいて、 最適なタイヤ交換を実現してそのときの最速タイムを求めるという問題。 タイヤ交換ができるチェックポイントは100箇所ある。 探索すれば明らかに2^100かかる。 これはDPだな、ということで頑張って考える。 進まなくなったので、問題を読み終わったM氏も一緒になって考える。 チェックポイントごとに明らかに劣っていない全候補を持ちまわるなど考えた。 そうこう考えているうちに、チェックポイント*タイヤの消耗度で行けるんじゃないかと 考え出す。 考えをM氏と話し合っているうちにどんどんアルゴリズムが現実味を帯びていって、 およそ数分のうちに同時に実現可能な解へと至った。 後はそれを私がコード化可能なアルゴリズムへと具現化するだけ。 最終的に得た解法は「ある地点にてある消耗度でやってきた車が残りを完走するのに必要な時間」 を求める関数を書くこと。 このタイプのプログラムは私が最も得意とするものなので、 本当に一瞬でコーディングは終了。 一箇所タイヤチェンジのコストを入れるのを忘れていてバグが出たが、 特に手間取ることなく完了。Submit、Yesを得た。
この時点で2時間過ぎ。5問正解。相当なハイペースだ。 このあたりで首位に立っていたような気がする。 (スコア見てないから分からないけど) 次の問題どうするか決めるために周りを見渡してみる。 うちが解いていなくて、ほかのチームが解いている問題を探したところ、 Powderysnowが白い風船(問題H)をあげていた。 …というか、あげているように見えた。 後で知ったことだがあれは白風船では無くて桃風船だったようだ。 いや、しかし。どこからどうみても白かった。 白かったので、問題Hは解ける問題だと思った。 (それもそんなに時間をかけずに) というわけで、問題Hを説明してもらう。 問題Hはビンゴカードが与えられるので、 数を読み上げる順をいかさまして特定の順でビンゴさせる、という問題。 しばらく考えてみるも解法は浮かばず。 結局分からないので、このあたりでほかの問題を全部教えてもらうことに。 まず、問題D。線路がと列車の配置が与えられるので、 指定した配置に変更するのにかかる手数を求めよという問題。 手数は最大で6。探索は間に合わなさそう。 次に問題G。ツリーのノード間の距離行列が与えられるので、 ツリーを復元しろ、という問題。全く解法が浮かばず。 最後に問題I。どこからどう見ても幾何最難系問題。絶対に手を出すな。
さて、どうするか。 考えないことには仕方が無いので、私が(すでに解かれていると思われた)問題Hを、 M氏とK氏が問題Gを考えることになった。 問題Hをうんうんと考える。だめだ、分からん。 十分ぐらい経っただろうか？M氏がGの解き方が分かったという。 まず、全点間を単なる直線でつないで与えられた距離行列を 自明に満たす"グラフ"を作る。それから、ノードをマージしてツリーを復元する… というものだったが、私がすごい勢いで？矛盾点を指摘。 ならばこうすればいい、と変形アルゴリズムをどんどん示されたが、 もはやアドホックすぎて全く正しいようには見えなかった。 そんな中、K氏が別のアルゴリズムを提言する。 それは、まず二点を条件を満たすように線で結ぶ(間に余分なノードを挟んで)。 それから、与えられた距離を満たすように点を追加していく、というもの。 追加するのは最初の直線を幹とすると枝に相当する位置に限るらしかったが、 それでは駄目っぽい例がいくつも浮かんだのでそれを指摘、 K氏が回答に紛糾していると、M氏が突然いける、と言い出した。 そのアルゴリズムは基本的には同じくノードをひとつづつ追加していくもの、 でも、追加する場所を決めるのに、各ノードからの距離(のインバース)を計算し、 その値の等しくなった場所にその値と同じだけのノードをはさんで追加する、というもの。 このアルゴリズムの正しさは自明ではないだろう。 すぐさま反例は思いつかなかったが、とりあえず証明を求めたところ、 追加できる点があるのならば、それは一点しかない、という証明は分かった。 ツリーが構成できるなら、追加できる点がある、という証明もできるようだが、 ちょっと私には難しくてよく分からなかった。 まぁ、あっていると言うので、信じて実装するしかない。 しかし、これは実装の重い問題だ。解法がわかっても作るのが大変で大変で…。 これを作っている途中でGNCがこの問題の風船を上げた。 IHIが問題Dの風船を上げた。 ああ、このままではいかん、と必死にコーディング。 解いている途中に、M氏が問題DとHの解法を両方思いついたと言ってきた。 うーん、これはもたもたしているわけにはいかん、と言うことで、 多分これも30分ぐらいで完成。 完成したコードはバグ多し。 ちまちま直してサンプルが通る。 Submit、返答はYes。
次はどっちをやるか。 問題Dの方がやりやすそう、と言うことで、問題Dに。 解法は、両側から探索、以上。ああ、たしかに盲点だった。 去年の愛媛でも同じ方法の問題がでたよね。 計算量の検証を聞くと、1ステップで最大百数十。 それらのノードのインターセクションを取る。 各データはかなりでかくなるが、GCC4の超最適化を信じて普通に実装することに。 しかし、これも解き方は簡単でも実装は重い。 というか、こんな問題を二連続で書くのはいやだ…。 ここから、問題の考察が終わった(問題Iは考えなくてもいいだろう…)M氏も加わって DualXP(？)体制になる。 いきなり線路データがめんどくさい。 ノード番号偶数右、奇数左とかに適当にマッピング。 ノードデータはset<vector<string> > で持つことに。 プログラムはアルゴリズムの外周部分から作っていく。つまりは頭を使わないところから作っていく。 外周部分が出来上がり、子ノード生成部分に。 ややこしい。移動を4通り記述、あっているか非常に不安。 何とかコードは完成。これも小さなバグが何個かあった。 サンプルが通る。でも不安なので、子ノードを出力してみる。 あっていそう。Submit。ジャッジはYes。 (この問題、後から時刻を見直したんだけど、 前の問題から36分で通っているのね…。 正直自分でもびっくり)
正解数7問、残り時間一時間。 周りを見渡すとNimrodとうちが7問正解。 ほかには7問正解はおらず。 あと問題Hを通したら間違いなくNimrodに次ぐ順位にはなれそうだった。 このまま7問で終わったら…正直分からなかった。 いろいろ考えていても仕方が無いので、残る問題Hを解くことに。 M氏からアルゴリズムを教えてもらう。 まずはあがらせるシナリオを指定(10^4)、 それぞれについてありうる並びを試す(4^4?) さらにそれを検証、と言うものだった。 ありうる並びの部分を普通に行っていては到底間に合わないので、 なんだか技巧的なことをやるみたいだが、 その説明が分かりにくいことこの上なし。 やっとわかって実装開始。 しかし、これも実装が重い…。 三連続でこんなの、もういやだ…。 とも言っていられず、やっぱり実装を頑張る。 それで、中盤まで実装が済んだとき、なんだか良くわからないことになってしまった。 アルゴリズムがあっていないような気がする。 というか、そのやり方でどうやって全パターン試すの？ この辺で残り25分ぐらい。 再度説明を受ける。説明を受けるも、説明も怪しくなってきた。 残り15分ぐらい。 なんかそれややこしすぎないか…？ 今からじゃ間に合いそうに無いよ… きっとPowderysnowはもっと簡単な方法で解いてるって(まだ勘違いしている)。 残り10分ぐらい。 ああ、もう間に合わない。 不完全だけど、もしかしたら正解するかもしれない方法でコードを簡略化することに。 残り5分ぐらい。 コードは完成。サンプルが通らない。 少なくとも一つ目は正解するはずなのに…。 残り2分。バグは取れた。しかし、サンプルの一番最後が合わない。 コードは正しいはずだから、間違っているのはアルゴリズムだ。 残り1分。ええい、もうどうにでもなれ。 ミラクルメソッドで最後のサンプルの答えを補正し、 ジャッジに送りつける。 「通っちゃったらどうしよう」 そして、時間終了。 しばらくして帰ってきた回答は No-Wrong Answer であった…。
終了後、私は5時間の間一切キーボードの前から離れていないことに気が付いた。 それから、とてつもない疲労感に襲われた。 それはそうだ、だって、立て続けに8問分もコードを書いたんだもの (特に終盤 G,D,H のコンビネーションはやばかった…)。 とりあえずスコアボードを見てみることにした。 最終的な風船の数は、Nimrodが8個、うちとPowderysnowが7個、あとは6個以下のようだった。 Powderysnowよりはどう考えても時間は勝っていたはずだ。 スコアボードを見てみると案の定うちのチームは2位につけていた。 3位とは300分の差がついていた。
その瞬間、私はおかしいぐらい自分の顔が笑っているのが分かった。 ああ、本当に勝ったんだ。よくやってくれたチームメイトに感謝。 そして、頑張った自分に、ご苦労様。
こうして振り返ってみても、やはり今回は大変だった。 かなりうまく行った様に見えるが、それでもこの成績である。 終盤、うちの7問正解が確定した時点で時間ではNimrod以外には勝っていたように思ったし、 ほかの日本チームが8問正解になるとは考えられなかったので、 少なくとも日本一にはなれたかな、とは思っていた。 そういう意味で、今回は割りと最後まで落ち着いてやれたのではないかと思う。 それでも、やはり最後に問題Hを通せなかったのはつらい。 終了後のパーティーにてNimrodに問題Hの解法を聞きに行った。 それを聞いたM氏によると、彼らはかなり時間が残っていたらしく、 いろいろ最適化を考える余裕があったようだ。 まぁ、考えてみればあの程度の複雑さのゲームで、 ビンゴゲームなのにサイズが4*4までと言うことからして、 探索+枝刈だと確信しなければならないのだろう。
終わったあと、今年は観光ではなく学校説明会があった。
正直言って観光がしたかった。いろいろ人生の足しにもなるのですよ。
それから、今年もいろいろな人にお祝いして頂いた。
レセプション会場に着いたらなんと湯浅先生が来て下さっていた。
体調を崩されていたようなのだが、うちのチームの成績をみて駆けつけて下さったらしい。
感激である。
それから、表彰式。
今年はFirst Placeとして表彰された。
やはりうれしいものである。
一位の賞品は(去年のマウスフォンの悪夢を微塵も感じさせない)
iPod shuffleだった(いやあ、ICPCで実用品をもらってしまいましたよ)。
そのあと、記者の方にインタビューを受ける。
私はこういうインタビューを受けるのは初めてだったのだが、
世界大会に対する意気込みなど、率直な胸の内を語った。
さらに今年は上位者にコメントを(無論英語で)発表する時間が与えられた。
ライバルと切磋琢磨した結果、強くなれました。のようにコメントしたと思う。
ひとまずは良い結果に終わってよかった。 しかし、ここからが本当の始まりだ。 去年の雪辱を晴らせるよう、もっともっと頑張ろうと思う。 最後に。これまで私を支えてくれた人たち、練習会を企画してくれた スタッフの皆さん、GNCの皆さん、一緒に練習して頂いた方々に。 ありがとうございました。