ARC229 B - Halving Subtraction

考え方

数列の各値は、操作で減ることはあっても増えることは絶対にない。
ということは、一度でも負の数ができてしまった時点で、それは不可能ということになる。

さて、この操作だが、$x$ が半分（切り捨て）になるというのは、右にビットシフトと言い換えられる。
ということは、ある $x_0$ を選んでの操作は、ビットごとに分割して考えても（回数以外）同じ結果になる。
例えば、$x_0=11$ での操作は、$x_0=8$ と $x_0=2$ と $x_0=1$ の $3$ つに分割して行ったと思ってもよい。
さらに、異なる $x_0$ での $2$ つの操作の順番を入れ替えるのも、明らかに結果に影響しない。

ということは、$x_0$ の値を $2$ の累乗に限っても、操作の本質は失わない。
つまり、以下のような $2$ つの操作だけで考えても、回数以外は本質的差異がない。

• 数列の好きなところを $1$ 減らし、その前を $2$ 減らし、その前を $4$ 減らし、以下先頭まで繰り返す
• 末尾を $2$ の累乗数だけ減らし、その前を $2$ 倍減らし、その前を $4$ 倍減らし、以下先頭まで繰り返す

さて、末尾を $0$ にするには後者を活用するしかない。
そして、同じ $2^i$ を $2$ 回選ぶのは $2^{i+1}$ を $1$ 回やるのと結果が変わらず、考える意味がない。
よって、まず最初に末尾を単純にビットで分解し、それぞれを削除して末尾 $0$ 状態にする。

すると、末尾の $1$ つ手前は、残りを前者で消すしかない。
つまり、残っている数と同じ回数だけ前者を行う。
続いて、さらにもう $1$ つ前も同様。
以下これを繰り返して先頭まで続く。
この途中で負の数が登場したら、不可能と判定する。

さて、ある $x_0$ を選んでの操作は、ビットごとに分割しても（回数以外）同じ結果になる事実を思い出す。
これは、$2$ 種類の操作は、内容が違うものを好きなだけ同時に $1$ 回に圧縮して実行できるということ。
つまり、同じ操作をやらなければいけない最大個数が答えである。
愚直にやれば $1$ ケース当たり $O(N^2)$ となる。

どんな操作でも基本的に後ろの $2$ 倍減ることを利用すると、高速化もできる。
$A_i-2A_{i+1}$ の値が $k$ であれば、ここをスタートとする前者の操作は $k$ 回必要ということ。
よって、以下のうちの最大値を求めればよい。

• 各 $i$ についての $A_i-2A_{i+1}$ の値（$1$ 回でも負の数が出たら不可能）
• 末尾が $0$ なら $0$、そうでなければ $1$

これで $1$ ケース当たり $O(N)$ となる……が、$N$ は高々 $30$ なので高速化の価値はあまりない。
書きやすいと感じるならこちらで、くらい。

入力例1での動作

入力例1のうち、まず $4$ 番目のテストケースを考える。

入力を受け取る。

n: 5
a: {16, 7, 2, 1, 0}

末尾は $0$ なので、末尾に由来する必要操作回数は $0$ 回として始める。

各 $i$ について $A_i-2A_{i+1}$ を順に求める。

すべて非負なので、全要素を $0$ にすることは可能である。
また、必要操作回数の最大値は $3$ なので、答えは $3$ となる。

次に、$2$ 番目のテストケースを考える。

入力を受け取る。

n: 2
a: {0, 1}

末尾が $0$ ではないので、まず必要操作回数を少なくとも $1$ 回とする。

唯一の差を調べると、$A_1-2A_2=0-2\times1=-2$ となる。
これは負なので、末尾側を必要なだけ減らそうとすると、その前の要素が負になってしまう。

したがって、このテストケースでは全要素を $0$ にすることは不可能であり、答えは $-1$ となる。

注意点

特になし。

別解

特になし。