ABC188 F - +1-1x2 (600)
コンテスト中の考察1
上の方のbitが揃うようにXに1を適当に加えながら2倍する
2倍できなくなったら後は差分を足す
実際には引くことで操作回数を減らせる場合があるので駄目
コンテスト中の考察2
逆から操作する方が操作のパターンが減りそうなので逆から操作する
calc(Y)でYにするための操作の最小回数を考える
$ Y \le Xなら操作は-1しかしようがないので$ X - Y回
$ Y \equiv 1 \left(\mod 2\right) ならmin(Y-X, min(calc((Y-1)/2), calc((Y+1)/2))+2)
それ以外はmin(Y-X, calc(Y/2)+1)
計算量が$ O(Y)になるかもと思いつつ提出したらAC
提出後に計算量が最悪になりそうなケースを考えていると$ O(\log Y)になりそうと感じた
手元で実際に試しても$ 2 \log Y位の回数になった
解説の考察
上の操作で$ d 回目で取り得る最小の値は$ \frac{Y}{2^d}-\frac{1}{2^d}-\frac{1}{2^{d-1}}- \cdots - \frac{1}{2} \gt \frac{Y}{2^d} - 1
上の操作で$ d 回目で取り得る最大の値は$ \frac{Y}{2^d}+\frac{1}{2^d}+\frac{1}{2^{d-1}}+ \cdots + \frac{1}{2} \lt \frac{Y}{2^d} + 1
$ d回目で取り得る値は整数なので、最大で2つ
$ \frac{Y}{2^d} - 1と$ \frac{Y}{2^d}の間の整数
$ \frac{Y}{2^d}と$ \frac{Y}{2^d}+1の間の整数
操作回数は$ O(\log Y)