http://agc015.contest.atcoder.jp/tasks/agc015_d
解法
http://agc015.contest.atcoder.jp/submissions/1314294
考察パートが長い。
大切な事実は以下の通り
- AとBのprefixが同じ部分は削除して考えて構わない。なので、数え上げをする前に同じprefixは消す、正規化をしておく
A = 1100101 B = 1110000 であれば、どうやってもできる数は11?????となるため、抜いて考えていい
こうすることで、最上位ビットが必ず異なるようにできる
- A未満の数は作れない
- 興味があるのは、10,100,1000のような数であり、これが登場すればそれ以降は組合せで作れる
0000 0001 <- 0010 <- 0011 0100 <- 0101 0110 大切なのはこの部分で、この3つがあれば、0000～0111は自由に作れる
大切な方針「A≦1000…≦Bな1000…をCとしておくと、[A,C]と(C,B]は分けて考える(変数line)。
- まず、[A,C]はそのまま答えに突っ込んでおく
- 次に、(C, B]の中で最大の100…を探す(変数line2)
- 例えば、line2=1000であれば、0000～1111は作ることができることが分かる
- あとは、それに加えて、[A,C]orCとすることで、より大きい数が作れる場合も答えに加えておく
これで答えが求まる。
A==Bのときとか、正規化したらA==0になっちゃったときの処理とかをこまごま書くとAC
