2012/05/27(日)Google code jam Round2

はてブ数 2012/05/27 02:01 計算機な日記::プロコンつーさ

参加した。14ptの1614位 泣いた。

Aは読むのが大変で、なんとか15分くらいかけて読み終わってDPすりゃ解けんのかなーと思ったけど、
いや、普通に一番遠くにたどってけば行けるかどうか判定できるのかって勘違いしてdijkstra書いた。
incorrectもらって、1分考えて反例に思い至って、多重化dijkstraに改造したら、当然ノード数爆発。
各つるで前に探索した時より遠くにreachできるなら続行みたいな改造したので、
Best First Searchじゃなくなっちゃった。largeの計算が終わらず……。辛抱して待つこと4分。
プロンプトに戻ってきた。提出。おお怖い怖い。通った。

Bが今までやったことないタイプの問題だった。
敷き詰める。5倍かー。結構広いんだなと思ったけど、コーナーケース考え出すとキリがない。
フィールドも広いからデータ構造作るのも大変だし。うー、どうしよう。
つーか、この広さなら貪欲でもたぶん大丈夫なんじゃねーの、自信ないけど。
3回出したがincorrectだった。smallだけでもほしい。N10ならモンテカルロで行けるんじゃね？
あと15分。今の貪欲をなんとか直すべきか、迷ったがデバッグの道を選択して、そのまま時間切れ。
一瞬脳裏をよぎった声に従って、乱択で行けばよかったのだが、SRM脳は乱数使う勇気がなかった。
ローカルで答えが合ってるかどうかわかるんだから、探索が終わるかおわんないかの運試し。
N<=10^3の方だってどっちにせよ運ゲーだった。
Aをもうちょっと早く解いて「この調子この調子」でBに取りかかれればまた違ったんだろう。

というか、こうやって振り返るとAもBも不正解じゃねーか。

Tシャツが欲しかった。可能性はあったと思う。つくづくTシャツには縁がないなぁ。

最近TopCoderのレーティングも立て続けに落としてるし、競技プログラミングがスランプ気味。
書くコードも汚くなった。僕のプログラマ人生はぼちぼち終わりかけてるのかもしれんとちょっと思う。

コメント（0件）