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; }