Xmas Contest 2016 A解説

Aの解説です。


f(X) = Xを超えない最大の2冪とする。(例えばf(70)=64,f(1)=1)
以下のような手順で質問を投げていけば良い。

  • 最初にf(N)を投げる。残る区間の長さはN-f(N)で、これは最上位bitが消えた数である。
  • 現在の残る区間長をxとする。xの上位2ビットが
    • 10....の場合、f(x)を投げる。残る区間の長さはx-f(x)になり、桁数が2桁減る。
    • 11....の場合、f(x+1)を投げる。残る区間の長さはf(x+1)-xで、正負が逆転する。桁数は、....の部分が0の場合は1桁減って2冪数が残り、0でない場合は繰り下がりによって2桁減る。

例えば二進数表記で N=1110111 のとき以下のようにクエリを投げると4回のクエリで総和がA+B-(C+D)として求まる。

f:id:snuke:20161226233628p:plain

青はクエリの区間、緑と赤は今和を求めたい区間で、緑は正、赤は負。

最上位bitと「....の部分が0の場合」は1桁、それ以外の場合は2桁ずつ減らすことが出来ることを考えると、10回かかるNの最小値は1(10)(10)(10)(10)(10)(10)(10)11となる。