ACM/ICPC 2006 アジア地区予選 横浜大会 結果
ACM/ICPC 横浜大会 に参加して帰ってきました。結果（速報）はこちら。僕らのチーム Hanafuda Shuffle GIVEUP orz は意外と健闘できて10位でした（まともな成績が残せてしまった）。日本チームでは8位。日本の私立大学では1位なのかな。アジア地区予選初進出の大学としては満足できる結果だと思ってます。
今回の僕らのチームの様子をいちおう書いておきます。
問題Aは僕が担当。オセロをやっている他の二人が問題Cは解けそうだということで取り組み始める。僕が問題Aのプログラムを書いてる途中にふと「サンプル入出力セットをダウンロードしてないや。」と思い浮かぶ（割り込みがあるのは集中できてない証拠だなぁ）。サーバにアクセスを試みるがつながらない。始めはGoogleの検索にリダイレクトされて何なのか分からなかった。ネットワークが落ちてるんだろうということに気付く。かなり焦りながらスタッフを呼んで，いろいろ話して結局リブート（確かスタッフの方がLANケーブルの配線いじってたかな？）。今度はちゃんとつながる。サンプル入出力をダウンロード。そしてソースコードを保存するのを忘れてたことに気付く。(笑) 気を取り直して書き直し。たしか80%くらい書いたところでふと「あ，リブートしたからPC2ログインしてなかったな。ログインしとこう。」と思い浮かぶ（割り込み多すぎ）。…ログインできない。また落ちてる。もう一回スタッフを呼ぶ。そして再リブート。今度は再起動してもネットワークにつながりません。NICが死んだらしい。とりあえずスタッフに任せて他の問題文を読んでアルゴリズムを考える。机の反対側でスタッフが喋ってたのでよく分かってないけど，最終的にはハード交換したのかな？すでに書いてるソースコードを退避して，PC交換して，スタッフの方がアカウント作ったりなんやらして，ソースコードをもっかいコピーし直して，復旧。A問題の残りのソースコードをさくっと書き上げてバグなくそのままTest＆Submit。通った。この時点で72分でした。周りはみんな問題解いてたので風船無くて寂しかった。救済措置は結局無しだったのかな？
キーボードを他の二人に渡してB問題とD問題を読む。B問題はすごく有名そうな問題。分かってたらさくっとやれるんだろうなぁと思いつつ，一度読んだだけでは解法が思い浮かばなかったのでパス。D問題は他のチームがかなり解いてて簡単そうだというのが判明するも，ちゃんと読んでもすぐに解法が思い浮かばなかったのでとりあえず他の問題を読んでみようかと思ってパス。コンテスト終了後コーチ陣からもっと簡単な問題（＝B, Dなんでしょう）を解かずに何F解いてんだと言われましたが，これが結果的によかった。問題Eは読んですぐに「絶対手を付けてはいけない問題」と判断してパス。
問題Fを読んでグラフ系DPでいけそうと判断。変形ダイクストラでどうだろうとちゃんと考えてみる*1。n=1000だし5ステップくらいまでの計算量を出してみてこれは実際に解けそうだということで紙の上でソースコードを書き始める。アルゴリズムは辿ってきた経路の状態を持ちまわすダイクストラ。動的配列を使うために2ヶ月以上触っていないし元々うろ覚えのC++を使う。vectorの要素数を求めるメソッドも記憶から抜け落ちてるままのすごく見切り発車。これも結果的によかった。
紙の上でC++コードを書いてる間にCがAccept。交替してFのプログラムを打ち込む。他の二人がDに取り掛かる。その後何度かキーボードを交替して交互にデバッグしながらFが完成。サンプル入力が通ったのでSubmit。WA。サンプル入力が通ってるのにWAはありえないと思ったらD問題のソースコードを提出していたのに気付く。気を取り直してSubmitし直してAccept。ちなみにローカルでの実行時間は10秒〜20秒くらいというぎりぎりに近いものだったと思います。Cで書いた優先度付き待ち行列が遅いべたなアルゴリズムを使ってるからそれのせいで遅くなってるのかな。この時点で（そして最後まで）F問題を解いているのは上海交通大学とうちだけだったので，変にはまらなかったのはラッキーでした。
この時点で1時半。終了は2時なはず。G，H，Iの問題をとりあえず読む。G＜H＜Iの難しさだと判断。とりあえずIは捨て。しかしこの時点で後20分じゃ新しく問題を解くのは厳しそうだと思ってDに参加。特に何もできずに他の二人がアルゴリズム変更とデバッグを完了してAccept。この時点で1時45分くらい。チームメンバの一人がBの解法を思いついたというので合ってるかどうか分からないけどとりあえずコーディング。多分5時間中この10分間だけフルに頭が働いてた。あかんやん俺。2時を過ぎても終わらないなぁと思いつつ（開始が遅れた分だけ伸びてたのかな），そのBの解法は間違えていることが分かってどうしよかーというあたりで終了。
お疲れ様でした。Hanafudaのメンバーはこれで全員引退です。二人ともありがとう。そういやチーム結成自体は国内予選の締め切り直前だしチーム練習も数えるほどしかしてないし。よくここまでいけたなぁという思いはあります。
しかしC言語メインで解いてたアホなチームは上位陣ではうちくらいじゃないでしょうか。なぜか本番始まってから慣れないEclipseをエディタとして使ってみたらどうやろーとか言い出してたし。(笑) 精一杯楽しんでくるという目標は十二分に達成できました。
さて，日常に戻ろうか。
