Google Code Jam 2008 QR - プログラミンギング

zonugataで参加してきました。

GCJ, TopCoder併せて練習含めて30問くらいしか解いたことない私が
そのレベルでレビューします。

フツーにDPを使う問題ですよね。
DP知ってれば簡単だけど、知らないと結構面倒かも。
でも頭悪いしDPのコード書くの3年ぶりくらいなので
再帰のコード書いてDPに変換するときに
エンバグして3回もトライに失敗した('A`)
もっとも、そのうち一回は
ルールよくわかってなかったせいですけど。

よくわかんなかったのでイベントをキューイングしました。
最初multipmap使ってみたら、
arrival+turnaroundとdepartureが同時刻の時に
バグったらしいのでmapに変えたところ
特に問題なく解けました。
ゲームプログラマ的には一番楽な問題かも？

苦手……　ＱＲじゃなかったら多分
見た瞬間あきらめてた

空白地の面積を合計してたんですが、
場合分けバグってて
アルゴリズムは初期からほとんど変わってないにも関わらず
デバッグにすげえ時間かかった

モンテカルロも一応試してみたけど
全然無理ですね

とまあなんとか、6点ともパスしたようです。

……と書いた後他の方のページをみたら
全部解き方違っててびびった。
Saving the Universe、DPいらないのか。

2005年度はQR通過(1000人くらい？*1 )で結構うれしかったけど
今回は時間制限も足きりスコアもすごく緩くて
7000人も通過してるようなので
次からですかね。

一問間違って別のソースsubmitしちゃった気がするけど、
大丈夫かな……　まあ通過は大小1つずつでいいみたいだから
どうでもいいか。

*1:今調べ直したら500人だった　ずっと勘違いしてたらしい