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)*2を投げる。残る区間の長さはf(x)*2-xで、正負が逆転する。桁数は、....の部分が0の場合は1桁減って２冪数が残り、0でない場合は繰り下がりによって2桁減る。

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

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

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