Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-04

RedIsGood (SRM420 DIV1 Medium)

| 16:27 | RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ

4時間かかってやっと解けた。できたコードは30行ほど。4時間で30行って、だめすぎるプログラマだ…。

思考経路

  1. 再帰で解いていけばいいはず。効率よくするためにキャッシュいるよね。
  2. R, B の箱を作って、その中に期待値を突っ込んでいけ。
  3. 期待値の算出をしばし悩む。
  4. やっとできた。時間遅いけど、手元だと動くよね。
  5. TopCoder 鯖で実行すると、std::bad_alloc で落ちる。double×5001×5001 でメモリ足りない。ざっと200M か…。
  6. 困った。
  7. 困った。
  8. 困った。
  9. 動的計画法に変える。あれ、それでもメモリ量変わらん?
  10. あ、R, B の値を求めるとき、R-1, B と R, B-1 が分かれば十分なのか
  11. ということは、左上から順番に計算していけば、ほとんどキャッシュする必要ない。
  12. しばしコーディング。
  13. 慣れてないので時間かかる。
  14. できた。すぐ終わる。すごい。

感想

再帰だと上手くやらないと時間かかったりメモリ食いすぎたりする場合も、動的計画法だと簡単に書けた。具体例を実感できて有意義だった。まだ動的計画法に慣れていないので、いつ使うのか、どうやって使うのかが直感的に思いつかない。繰り返せば慣れるのかなぁ…。

TopCoder SRM 420 Div1 - chokudaiの日記(仮) がとても参考になった。ありがたや。

その後、早い人の解をみた。できたコードのエッセンスは同じだ。しかし、3分40秒で解いてるのがすごすぎる。コードが一瞬で頭の中にできあがって、あとは書くだけなんだろな…。