PRoxy Diary

_ [ICPC] アジア地区予選東京大会

なんと優勝してしまいました。これは本当に嬉しい。しかも最後の1分で逆転するというありえない展開でした。少々の運も有りましたが、勝てたのは僕がミスを出すたびに拾ってくれたチームメイトのおかげです。本当に今回はみんなの力を出し切ってもぎ取った優勝だと思います。

2位は東大のUnknown。ここのメンバーのushさんもnyaさんもkzk君もみんなみんな凄い人なので、正直勝てたのが驚きです。Unknownは、この調子で行けば台北で負けることは無いでしょう。来年もあるしねー。

3位は東大のMakegumi。会場ではちょうど斜め前の視界に入る席に座っていたので、たまにMakegumiの方を見て和んでいました。

コンテスト本番のことを少し振り返ってみたいと思います。問題はこちらから。

さくっと解いちゃった問題は余り印象に残っていなくて記憶が曖昧なので、順番が多少前後しているかもしれません。

A: Josephus問題。Nが10000まで来るので、うちはO(N)のDPを書いて通しました。問題Aにしては複雑なことをさせるなぁと思っていたのですが、開始1時間でかなりたくさんのチームが解いていたので、どうやらO(N^2)でも良かったようです。それを見て、Time Limitが相当緩いなと分かりました。

B: 正整数が与えられたら、その前後の素数を求めて差を答える問題。与えられた整数が素数なら0を出力。Aより簡単。やるだけ。

C: バックギャモンというゲームで一定ターン以内に勝利する確率を求める問題。バックギャモンの本当のルールをよく知らないのだけれども、これでは完全に運ゲーなのではないだろうか。解法としては単純DP。

E: A,B,Cを解いた時点でEまでしか読めていなかったので、次に解くならDかEという状況でした。Dは一瞬では解法が分からない。Eは解法は自明。ということでEを頑張ってみることにしました。線分の集合が与えられるので、それをグラフとみなして最短路を求めろという問題で、しかも線分が一方通行フラグも兼ねていたりと、実装がとても大変で泣きそう。しばらくしてコード自体は出来上がったものの、バグが全然取れないし、疲れたし、他に簡単な問題があるらしいということで、一旦放置してそちらに移ることに。

F: 無向グラフが与えられて、使う辺のコストの最大値と最小値の差が最小な全域木を求める問題。頂点数nは100まで。問題AでTime Limitが緩いということが分かっていたので、ナイーブにO(N^4 logN)でさっくり書きました。一回サンプルに合っていないのを間違えて送ってしまったけれども普通に通る。O(N^4 logN)から計算量を落とそうと思うと、尺取りメソッド+HenzingerのDynamic Graphの方法を使ってO(N^2(logN)^3)で出来るかな。などと一瞬頭をよぎるも無視無視。

E(2): もしかしたらEを通したのは、もうちょっと後かもしれないですがちょっと記憶が曖昧です。新たな気持ちでEのコードを調べると、一方通行の処理でグラフを破壊していたために、他の一方通行の判定が正しくなされていなかったことが判明。ここを直すと最短路自体は見つかった。ただまだ経路の出力が一致していなかったので、そのあたりのルールを再度確認して直して送ったら通った。

G: MakegumiがGを通しているのを見て、まぁ両側探索だろうなぁと思いひたすらコードを書く。次の状態を生成するコードを人数に依存しないように書こうとすると再帰関数を使うしかないと思うのですが、この問題で再帰はなんか重そうで嫌だったので、人数が1,2,3の場合の3通りを直に書きました。最後のサンプルで1,2秒かかっていたので、ちょっと遅いかなぁと思ったけれども、送ったら通った。普段Online Judgeに慣れていると、本番でTLEを殆ど喰らわないのでとても良いですね。

H: 次にやったのが多分H。配列の定義とその配列を使用するコードが与えられるので、まだ初期化されていない要素が使われていたり、配列のサイズより大きいところを参照していたり不正なことをしていないかをチェックしろという問題。周りがそこそこ解いているので、簡単かなーと思って書いてみて、実際サンプルに合うまではすぐだったのだけれども、何回送ってもNo - Wrong Answer。。。しかも手元で作ったサンプルは全部通るので、さっぱり分からない。コードを印刷してチームメイトにデバッグしてもらうことにして、僕は別の問題に取りかかることにしました。

I: 凸な多角形が与えられて、これを陸、多角形の外側を海とみなす。陸の中で、一番海から遠い地点の海からの距離を求めるという問題。聞いた瞬間にバイナリサーチ+ポリゴンカットで解けると気づいたので、あとは書くだけ。さっくり通る。

D: この時点で残り2時間ぐらい有った気がする。Hは任せとけばバグが見つかるだろうと思ったので、僕は別の問題に手をつけることにする。DとJがあって、Dは計算量の見積もりがしにくいのだけれども、流石に2時間も有れば最適化をする時間も十分有るだろうと思いDを解くことに。方針としては、最初に全てのl^2(1<=l^2<=80000)に対して、l^2=a^2+b^2という分解をすべて列挙しておく。こういう分解方法が一つのl^2に対してあまり多くないということを知っていたので、この性質を使うことにしました。三角形の頂点をp0,p1,p2とし、新しく作る点をq0,q1,q2とする。最初にq0を決め撃ってp1の距離を求めれば、先ほど求めた分解からq1の候補となる点が列挙出来る。同じようにq1とp2の距離を求めれば、先ほど求めた分解からq2の候補となる点が列挙できる。q0,q1,q2が得られれば、後は条件をチェックして高さを求めて完了という算段です。点と点の関係がとてもややこしいので図を逐一見ながらコードを書きすすめていって、30分か40分ぐらいでコード自体は出来上がっていたと思います。ただここからが長かった。。。サンプルには合ったので、送ってみるもこれまたNo - Wrong Answerの連続。。。なんでーなんでーとコードを見直すも全然分からないし、サンプルを作って試そうにもサンプルをとても作りづらい。

H(2): そうこうしているうちにHのバグが見つかった。

a[1]
a[0]=10
a[0]=a[0]

は正しいコードのはずなのに、僕の書いたプログラムでは3行目が間違っていると言われる。代入文の評価をするときに、左辺のa[0]にまだ値が無いよということを示すUNDEFというフラグを入れるようにしていたのだけれども、これが元々a[0]に何か値が入っていたとしても問答無用でUNDEFを入れていたのがバグの原因でした。この場合はa[0]には10という値がもともと有ったのだから、これを消しちゃまずい。これを直すと通った。

D(2): ここで8問、残り45分。Jを解くことは考えずに3人でひたすらバグを探す。他のチームの状況も気にはなったけれども、見ても焦るだけだと思ったので、まったくよそ見はしなかった。実は僕は本番中は自分が何位かを全く把握していませんでした。チーム全体としての動きはチームメイトに任せてあるというのもあるけれども、どうせ1位を狙っているのだから自分の順位によって戦略を変えるなんてことも無いし。あと目が悪くて、前方スクリーンのstandingsが見えなかったというのもあります(笑)。

ひたすらコードを精査することに集中する。うーん、全然間違いが見つからない。PC^2を見たらなんか残り時間10分とか書いてあるし。ここで通せないとOB/OG会の模擬アジア予選と一緒になってしまう。。。しかし模擬アジア予選の時と違ったのは、みんな最後まで諦めてなかったこと。練習の時はこういう状況になると、僕一人がバグ探しをして二人はぽかーん状態になることが多いのだけれども、今回は最後まで3人とも集中していた。その結果残り5分も無いような状況でおかしな例が見つかった！おうおう何でじゃとデバッグ出力を大量にいれてチェックすると、l^2=a^2+b^2で分解するときにa=0であっても構わないのにa>=1,b>=1なものしか列挙していなかった。理由がわかった時には、もうPC^2が残り1分と言っていたので、for (int a=1;a*a<=l;++a)となっているところを、for (int a=0;a*a<=l;++a)に書き変えて、もう他のサンプルに合うかどうかも確認せずにとにかくサブミット。その後、サンプルに合うことを確かめて、誤差関係をいじってもっかいサブミット。結果が帰ってくる前にカウントダウンが始まり、そしてコンテスト終了。。。

燃え尽きてぼーっとしていたら、唐突にウインドウが出てきた。Yesきたー。もしかしたら勝ったんじゃねとか思いつつも、もう全身が気だるくて周りの風船の数を数える気にならなかった。。。

その後は、コンテスト中にマシンの不調とか？で作業が暫く出来なかったチームの為に設けられたロスタイムがありました。うちのチームはロスタイムは無いのでただ休んでいるだけでした。あ、なんか青色風船が配られてきた。コンテスト終了30分前過ぎても風船配られるのね。チームメイトが他のチームの状況を確認してくれたところによると、どうやら9問解いたところは他には無さそうだとのこと。

ロスタイムが終わってコンテストが完全に終わると、コーチの大林さんとえぬさんと田中さんと今道さんが席まで来て祝福してくれました。

その後はICPCのアジアディレクターがやってきて、今までどれぐらい練習をしてきたかを聞かれました。後は世界大会の行われるBanffは奇麗なところだよとかそんな話。

去年の2位も嬉しかったのですが、今年の1位はもう本当に嬉しい。

表彰式で1位で呼ばれたときは、これまで猛烈に練習してきた記憶が蘇ってきて、ちょっと感傷に浸ってしまいました。たまには努力が報われることもあるのだなぁとしみじみ。今回は運も味方してくれました。

おそらくこれで世界大会には行けると思われます。世界大会はさらなる強豪が待ち受けていますが、今年こそメダルを取れるように頑張っていきたいと思います。