Hatena::Grouptopcoder

hotpepsiの練習帳

2017-04-09

SRM 711

00:06

Div1 Easy (250) ConsecutiveOnes

問題

  • N以上で、2進数表記で1がK個連続する最小の数を求める

方針

  • 1がK個連続している数(1 <<K - 1)をXとする</li>
  • XとNの上から1ビットずつ見ていく
  • Nが1ならXにも1を立てる(=N以上にする)
  • Nが0でXが1なら、Xのほうが大きいので終了し、仮の答えとする
  • Xの初期値を1ビットずらして(2倍にして)全て試す
  • 仮の答えのうち最小のものが答え
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_711/ConsecutiveOnes.cpp

結果

o-- +1 194.73 +50 = 244.73pt rating 1649 -> 1686 (+37)

とーらすさん記念の回。

方針が単純なのが良かった。無限ループする解を落として+1


https://togetter.com/li/1094091

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170409