Hatena::Grouptopcoder

hotpepsiの練習帳

2014-05-08

SRM 615

| 02:33

Div1 Easy (250) AmebaDiv1

問題

  • アメーバのモンテカルロは、自分と全く同じ重さのゼリーだけを食べる
  • ゼリーを食べると体重が2倍になる
  • ゼリーの重さが出現順に与えられる
  • モンテカルロが到達しない重さの組み合わせの総数を求める

方針

  • ゼリーに含まれない大きさだったときは何も食べないので無関係
  • ということはゼリーに含まれる大きさだけを考えればいい
  • 元々の大きさがaだったとき、最終的にa*2^nになるので、aが到達しない候補となる
  • a*1/2のゼリーが含まれているとaになることがあり、それを候補から除外する
  • まずゼリーに含まれる大きさにそれぞれについてシミュレーションしておく
  • ゼリーに含まれる大きさのうち、到達しないものを数える
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_615/AmebaDiv1.cpp

結果

o-- 211.75pt 323/727th rating 1439 -> 1477 (+38)

落ち着いて解けた。なかなか良い点数。

乱数は出てこなかった。


http://togetter.com/li/650989

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20140508