ABC 27 C - 倍々ゲーム ( Game theory, Adhoc )

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder

abc027 from AtCoder Inc.

www.slideshare.net
ちょっと面白かった。説明はスライドの図を見た方がわかりやすい。こういったアプローチは幾つか選択肢木を描いて考察した方がでやすいですね。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MAXN = 1e18 + 18;

ull n;

void solve(){
    int dpt = 0;
    ull nn = n;
    while( nn > 1 ){
        nn /= 2;
        ++dpt;
    }
    int left_odd_lose;
    if( dpt & 1 ) left_odd_lose = 0;
    else left_odd_lose = 1;
    ull v = 1;
    int oddLose = 1;
    dpt = 0;
    while( true ){
        if( left_odd_lose ){
            if( dpt & 1 ) v = v * 2;
            else v = v * 2 + 1;
        } else{
            if( dpt & 1 ) v = v * 2 + 1;
            else v = v * 2;
        }
        if( v > n ) break;
        ++dpt;
        oddLose ^= 1;
    }
    string s[] = { "Takahashi", "Aoki" };
    cout << s[ oddLose ] << endl;
}

int main(){
    cin >> n;
    solve();
    return 0;
}