問題
整数をビット表現した際の右から0が連続する数の配列が与えられる。この配列の条件を満たしながら、実際の整数でも1ずつ増加してる数列を増加数列と定義する。
増加数列となる要素数を求めよ。
解法
増加数列には、あるパターンが存在する。
3 : 0 1 0
7 : 0 1 0 2 0 1 0
15 : 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
与えられる数列の長さは50以下なので、7以上の数字は6として扱うことができる。この条件を用いて条件を満たすかを全探索する。
計算量