東京大会

miracです、お久しぶりです。

この土日にICPCの東京大会に参加してきました。

結果はこちら。
http://icpc2010.honiden.nii.ac.jp/regional-contest/standing

従来のような "アルゴリズムは簡単だが実装が大変" という感じの問題が減って、

"実装は普通だけどアルゴリズムをしっかり考えないと解けない" 問題が増えたかな、

という感じです。


タイムラインはこんな感じ。

開始 5分前:
チーム内で「勝ちを狙わず楽しんで解きましょう」と話し合い

開始 20分:
例年通り A問題が簡単だったので、mirac が実装して提出。TLE (速度が遅く、不正解) 。
nkamae から修正案をもらったので修正を開始。

開始 35分:
A問題を修正して提出。AC (正解) 。
kaming と nkamae がB問題を考えていたので、そのアルゴリズムを確認。
よさそうな感じなので nkamae と交代。
mirac は他のチームがよく解いていたFを考える。

開始 55分:
B問題を nkamae が提出。AC (正解)。
Fがさっぱり分からんので nkamae に丸投げ。自分はDを考える。

開始 75分:
nkamae がFの大まかな解法を説明してきたので相談。
そのままでは解けない事が分かったので、
相談しながら15分ぐらい (?) かけてアルゴリズムを修正。
問題を読んだ mirac が入力部分を、それ以降を nkamae が実装。

開始 110分:
問題の本質ではないところが無駄にバグってたので、ひたすらデバッグ。

開始 125分:
バグがとれたっぽいので再度チェックして提出。AC (正解) 。
他の問題を読んで考えていた kaming から、Gが簡単との説明。
典型的ダイクストラだったので、ダイクストラ担当の mirac が実装開始。

開始 155分:
Gの実装・デバッグが終了。提出。AC (正解)。
この辺の時間に何をしていたか、あんまり覚えてない(笑)

開始 ???分:
Hが解けるっぽいことが判明したので、実装開始。

開始 ???分:
だらだら書いていたHの実装が終了。しかし"問題解釈が間違っていた"ことと、
"それを修正すると実行時間が8倍になる"ことが判明。
まぁやってみようかということで kaming と2人でプログラムを修正

開始 220分:
修正とデバッグが完了。最大ケースを入れると遅すぎたので一部高速化

開始 230分:
これ以上高速化する方法が思いつかなかったので、
TLE(遅すぎで不正解)にならないことを祈りながらHを提出。AC (正解) 。
Hを解いている間に nkamae がEを紙上でプログラミングしていたので、
そのアルゴリズムを確認して、交代。自分は再度Dを考える。
nkamae と kamingの2人でペアプロを開始。

開始 255分:
あと40分しかないのでDを考えることを諦めてEのデバッグに参加。
 
開始 270分:
Eのデバッグが終了。提出。AC (正解) 。
他チームに勝つためにはもう1問必要だということで、問題を選ぶ。
Dは多くのチームが解いているが、
3人ともアイデアがなかったので上位チームが解いているC問題を選択。

開始 275分:
終了まであと25分。
kamingがそれっぽいアイデアを提案。
3人で一般化したが証明できないので焦る。

開始 280分:
時間がないのでとりあえず mirac が実装開始。
あとの2人は証明を頑張る。

開始 290分:
実装する時間が十分にないことが分かったので、
先ほどまで言っていたアルゴリズムではなく、
"正しい可能性は少ないけど10分でも実装できるアルゴリズム"に変更。

開始 297分:
終了まであと3分。実装が終了。デバッグ開始。

開始 299分:
終了まであと1分。今まで実装していた"正しい可能性は少ないけど
10分でも実装できるアルゴリズム"に反例を発見。諦める。

開始 299.875分:
みんなでカウントダウン開始

開始 300分:
終了。チームメイト同士で握手。
8問ぐらい解くつもりだったのに、6問しか解けなかったのでちょっと涙目になる。

タイムラインはまぁこんな感じでしょうか。詳細はまた書くことにしますー。