hotpepsiの練習帳

SRM 546

23:35

Div1 Easy (250) KleofasTail

問題

• ある数値を、偶数なら1/2、奇数なら-1していく。
• 範囲AからBまでの数Xについてその操作を行う。
• 一度でも数Kが出現するXの総数を求める。

方針

• 一番下のビットが落ちていく
• 途中でKを経由するかどうかを判定する
• 上位のビットがKならOKっぽい
• ゼロはどうやら特別扱い
• 上位ビットがKでNを超えない総数を求めるf(N)を書いて、f(B)-f(A-1)でいける
• Kが偶数のときは、K|1もKを経由するので、それを考慮
• 一時間以上かかって提出
• (書き直し)
• Kをlower、K|1をupperとして、1ビットずつ大きくしていって、lower<=X<=upperとなるものを数えればよい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_546/KleofasTail.cpp

結果

o-- 95.63pts 362nd rating 1278 -> 1352 (+74)

久しぶりのプラス点。

だいぶ無駄なコードを提出してしまい反省。