[AtCoder]ABC027 倍々ゲーム

問題：https://atcoder.jp/contests/abc027/tasks/abc027_c

解法

$x = N$のところから考えていきます。

例として、$N = 10$の場合を考えます。

もし、$x$が10～6の時、$2x, 2x+1$のどちらを選んでも10を超えるので負けが確定します。

次に、$x$が5～3の時、$2x, 2x+1$どちらを選んでも、次は10～6と前述の負けが確定する範囲の数を相手に渡すことができます。つまり、5～3は勝ちが確定している範囲です。

次に、$x=2$の時、$2x, 2x+1$どちらを選んでも勝ちが確定している5～3の数字を相手に渡すこととなります。つまり、2は負けが確定します。

最後に$x=1$の時$2x$を選ぶことによって負けが確定している2を相手に渡すことができます。つまり、$x=1$は勝ち確定です。よって、高橋君が勝者となります。

このように$N$から勝ち負けの範囲を求めていくと上手く求まります。

一般化する

勝ち範囲から負け範囲を求める。

勝ち範囲の下限が$a$とします。この時、隣の負け範囲の下限は$2x, 2x+1$どちらを選んでも、$a$以上になってしまう数です。すなわち、小さいほうの手である$2x$を選んだとしても$a$以上になる数です。そのような数は、$\lceil a/2\rceil$(切り上げ)です。

負け範囲から勝ち範囲を求める。

負け範囲の下限を$b$とします。この時、隣の勝ち範囲はの下限は$2x, 2x+1$どちらかを使って、$b$以上にできる数です。すなわち、大きい方の手である$2x+1$を使った時、$b$以上にできる数です。不等式を変形することで求まります。小数点以下は切り上げです。

実装

解法にあるように、どちらの範囲を求めるにしても1つ前の下限が必要です。ここで、$N+1$の時、相手が既に負けている状態なので最初の勝ち範囲の下限とできます。

割り算の切り上げは$a/b$の時、以下の式で示されます。

今の範囲が勝ちかどうかをwinで管理しています。

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long n;
  cin >> n;
  n += 1;
  bool win = true;
  while(n > 1){
    if(win){
      n = (n+1)/2;
    }else{
      n = n/2;
    }
    win = !win;
  }

  if(win){
    cout << "Takahashi" << endl;
  }else{
    cout << "Aoki" << endl;
  }

  return 0;
}