ICPC国内予選でした
参加した皆様，お疲れ様でした．
結果ですが，5問を(ギリギリで)解いて7位でした．JAGの夏合宿にも多分招待されるはずなので期待です．
全体の順位：http://honiden-lab.ex.nii.ac.jp/events/icpc2010/common/guest_standings_en.php
とりあえず問題の考察とか．
A
開始直後．僕は#include
書き終える．で，チームメンバーの1人から説明を聞く．え… これでAとかちょっと重くないっすか…
とりえあずmap
チームメンバーのもう1人が書く．提出．ここまで15分くらいだったかしら?
B
印刷した問題文が降ってきたので，僕はCを読んで，チームメンバー2人がBを読むことに．
全然読んでないけど入力がなんか気持ち悪いし実装も大変そうだ…
C
読む．
…
何これ，ただのDPじゃん… Bよりも簡単そうに見えるしこっち先にやった方がいいのでは…．
→Bが印刷してデバッグしてる間にこっち解く．簡単． ここまで30分くらい．
B(再)
チームメンバーが通した．ここまで多分40分くらい．
その間に僕はDを読んでいた．
メンバーの1人がEを担当して分担することに．
D
わー，なんじゃこりゃ．…木構造作ってDFSとかすればよさそう．
重心の座標公式とか全然覚えてないけど，Σx座標×重み/Σ重み とか使えばできるはず．
→ チームメンバーの1人とペアプロしながら書く．実装がちょっと辛い．詰まる．
メンバーがEはベルマンフォードで解けるとか言ってる．印刷して交代．
E
なんか書いてる．
こっちのDをどうするかが大体まとまってきたので交代．
D
基本的にDFSを2種類やる．1つ目は連結成分を取り出すためのDFS．2つ目は，子のピース(自分より上にあるピース)に対して条件を満たしているかを確認するためのDFS．
書けた．ここまで70分くらい… だったかな．とりあえず提出．
WA．
うーん…
印刷してEと交代．
Dのデバッグ(泥沼)
なぜだ．なにがいかんのだ．
重心を求める過程で，割り算を結構している．もしかして，計算誤差?
…ないと思うけど一応x座標の総和だけを取るようにしてみる．(ブロックの重みは全て同じなので，最後に割るだけで良いはず)
結果は別に変わらない．
うーん…
コードとにらめっこ．印刷も結構しまくってる．
何も間違ってるところなさそうなんだけどなぁ… 1時間くらい見るけど何も分からない．順位も落ちてる．まずい，まずい…
あれ，子のピースを求める際のタイミングがこれじゃまずいんじゃないか? …これはまずい．直す．
これで通ったんじゃないのかしら．送る．WA．
えええ…
コードの至る所を疑う．
さらによく見たら地面に接しているノードがちゃんと取れてない．間違いだらけじゃんこれもういや．直した．
送る．WA．
なんでなのよ…
ん，違う．よく見たらこれサンプルに対する出力送ってるだろうが．アホか．
今度こそ一度ちゃんと送る．AC．一安心．
すぐに書けた割になんだかんだで1時間半くらいデバッグにかかってしまった．なんてこった．
E
完全に1人のチームメンバーに投げている状態．
とりあえず普通にベルマンフォードやったんでは無理だということが分かった．（文字列の+だと必ずしも最適性の原理が成り立たないから．つまり，文字列s1,s2がs1
少し拡張したダイクストラでやっているらしい．なぜそれでいいのかはよく分かっていない．（なんとなくそれで良さそうな気はするけど…）
時間ももうないし，デバッグもしないといけないだろうし，正直諦めていたのだけど，ここでなんと1つ目のテストケースが通ってしまった…!!
ここまでで時計の指す時刻は19:29．(終了は19:31)
アルゴリズムが重いのか，実行に結構時間が掛かる．間に合うか…?
2つ目のテストケースを急いで落とす．実行．やはり時間が掛かる．19:30とかになってる．やばい．急げ急げ．お，できた．提出．AC．
喜びすぎて教室で叫んでしまった．
感想
全体的に難化したんじゃないでしょうか…．
Aからまず難しい．その後もC以外は実装が重い問題が続くし，楽ではなかったと思います．
参加チームの1/3が0問ってのはどうなの…って気がしなくもないです．というかこの難易度だったら別に6問で良かったのでは．
問題セット自体はとても面白い問題が多かったと思います．
A〜Cは探索やDPの基本的なアルゴリズム(+やや重い実装)，Dは少し応用的なDFS，Eは文字列をコストにするグラフという真新しい題材，という感じで考えていて楽しかったです．
Fはよく分かってません．Gはハードそうですが時間が5時間くらいあればできると思います．ほんとかよ．いつか解きたい．夏休みとかに．
個人的にはDのデバッグでかなり時間を食ってしまったのが悔しい．
Eがギリギリになったのはこれのせいもあるので，うーん，でもこんなのあまり対策しようがないしなぁ…
とりあえず今回は結果オーライな感じでアジア地区も頑張りたいです．目標は6問ACくらいで．
