Google Code Jam Qual

なんだかGoogle Code Jamに参加しておりました。
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw
予選ということで三問、時間は事実上無制限？
なんだか自分の老化が目立つ結果になった。
しかしまあ三つとも通ったので次にはいける模様。

A

貪欲に解けるだろうなあと思いながらも、頭が回らなかったので
涙目で確実なDPを選択。せっかくなのでHaskellを使おうと思ってたのだけど、
効率的なmemoiseを準備していなかったので、これまた涙目でC++利用。

B

貪欲にシミュレートするだけでいいと思ったが、完全にヨみきらず。

直感の七割は正しいので、そろそろそういう戦い方もしてみるかなあと。
サンプルインプット読み違えてて問題の理解に20分近くかかってたから
焦ってただけかもしれない。

C

正確に計算しようとしたら帯がとてもたくさんある場合に
計算時間が間に合わないかもしれないと思って
メッシュに切って適当に求めるのを書いたが、
別にそんなことは無いと仕様に書いてあると、書き終わってから気づいた。
そしてメッシュに切った場合、細い帯が間を開けて存在している場合に
誤差が出やすいことが発覚、よほど細かくするといけるが、
とても間に合わないので、涙目で帯状スライスに変更。
バグも出まくって、前半後半ともに40分ぐらいかかった。
あまりにもひどい結果。
サンプルの親切さに感動。