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秒で解いてるのがすごすぎる。コードが一瞬で頭の中にできあがって、あとは書くだけなんだろな…。

StringInterspersal (SRM414 DIV1 Medium)

| 00:16 | StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ

500点問題の練習。と思ったらすごく簡単だった。正答率50%。ま、そんなもんだろうな。番兵を最後におけばシンプルなコードになった。

CollectingPostmarks (SRM415 DIV1 Medium)

| 02:41 | CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ

制限時間に計算を終わらせる方法が分からない。そのまま調べると2^32通りになってしまう。案の定、System Test でタイムオーバー。諦めて模範回答を見る。

2分割する手法をとっている。

  1. 半分ずつ分割する
  2. それぞれの組み合わせで値と値段を求める(2^16×2=12万通り)
  3. それぞれの組み合わせで値でソート
  4. それぞれの結果を見比べて K を超えるものを調べていく(16^2=256通り)

なるほど。2分割してマージしてる。分割統治法か!

正答率14.58%。解けなくても仕方がないとするか。2^32 で解くところまでなら書けたので、あとは2分割することを思いつくかどうかだ。