Hatena::Grouptopcoder

TopCoder煮ブログ

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

2008-10-04

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分割することを思いつくかどうかだ。