ABC027 C - 倍々ゲーム

概要

整数Nが与えられる。高橋君、青木君の二人ゲームを考える。
・最初の整数を1とする。
・現在の整数をxとするとき、プレイヤーはxを2xもしくは2x+1に置き換える操作を交互に行う。
・先手は高橋君
整数がNを超えたとき、最後に操作を行ったプレイヤーを負けとする。勝つプレイヤーを答えよ。

制約

1 ≦ N ≦ 10^18

方針

解説通り。

2^d ≦ N < 2^(d+1) なるdについて下記が言える。
・dが奇数なら高橋君はx⇒2xの操作、青木君はx⇒2x+1 の操作のみを行う
・dが偶数なら高橋君はx⇒2x+1の操作、青木君はx⇒2x の操作のみを行う

この規則に従いシミュレーションすることで解答が得られる。

解答

Submission #6905069 - AtCoder Beginner Contest 027

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N;
	cin >> N;
 
	int d = 0;
	for(int i = 0; i < 63; i++){
		if((N >> i) & 1) d = i;
	}
 
	bool aoki = false;
	ll t = 1;
	if(d % 2 == 1){
		while(t <= N){
			if(aoki){
				t = 2 * t + 1;
				aoki = false;
			}else{
				t = 2 * t;
				aoki = true;
			}
		}
 
		if(aoki){
			cout << "Aoki" << endl;
		}else{
			cout << "Takahashi" << endl;
		}
	}else{
		while(t <= N){
			if(aoki){
				t = 2 * t;
				aoki = false;
			}else{
				t = 2 * t + 1;
				aoki = true;
			}
		}
 
		if(aoki){
			cout << "Aoki" << endl;
		}else{
			cout << "Takahashi" << endl;
		}
	}
 
 
}