ARC127 C - Binary Strings (500)
最初の文字は1
$ Xから1を引いて考えると、
$ X = 0なら終わり
$ X \lt 2^{n-1}なら次の文字は0
それ以外は次の文字は1
これで再帰的に解けるように見える
判定は今見ている最上位ビットが0かどうかで基本的に可能
ただし繰り下がりの実装が必要
実際には$ X \lt 2^{n-1}の場合にはもう一度繰り下がりが必要になる
$ X=0かどうかの判定を愚直にやると$ \mathcal{O}(N^2)かかってしまう
立っているbitの数を持っておいて繰り下がり処理毎にこれを更新
立っているbitが0個かどうかで判定することで$ \mathcal{O}(N)に