Google Code Jam

見事に予選敗退・゜・(ノД`)・゜・。
1000点問題はDropRocks（問題はこちら http://d.hatena.ne.jp/rich850/20000201）の方だったのだけども、まともに波紋をインプリメントしてたら解けないんじゃないかなどと勝手に早合点してしまい、なにかクールなアイデアがあるのではと悩み始めてそのままはまってしまってタイムオーバー。残りの400点のは普通に書くのが遅かった。
DropRocksといい、練習問題のものといい、1000点問題で座標やセルを扱う問題はどうやら時間が導入がされてくる点がポイントのように思う。時間が導入されることで検査する領域が3次元になるわけなんだけれども、ここでいつもの通り、一旦すべての検査したいものを用意してから、一番大きい（小さい）値をさがすという明確なステップを辿る構成で組もうとするとするとはまってしまう。ここが引っ掛けになっていて、大きな配列をつくってみたり、全件検索するループをつくるとメモリの制限や実行時間の制限をオーバーする仕掛けになっている。（練習問題の方はダイクストラ法を使うのが当然とすれば、大丈夫だけれども）普段やり慣れている、全部用意→検索、という考え方を捨てて、生成と検索を同時に同ループ内で行うというやり方を採用していかなくてはいけない。
具体的にはDropRocksを解くにあたっては、安直に波の高さを記録する2250*2250の配列や、時間軸まで入れた2250*2250*1000の配列を用意しようとせずに、その単位時間において波が発生しているところの高さを記録する座標をキーにしたハッシュリストを用意して、時間をひとつづつすすめ、その時点の波を生成し、ハッシュリストへ展開しながら最大波高を検査していくべきだった。