ARC 072 D - Alice&Brown
問題概要
2つの山にX,Y個の石が置かれている.
プレイヤーは一つの山から2i個(2<=2i<=XorY)とってもう片方の山にi個置くことができる.
石が取れなくなったら負け.
どちらのプレイヤーが勝つか.
1 <= X,Y <= 1018
解法
とりあえず実験してみる.
X<=1 & Y <= 1 の時は必敗で,B勝ち.
solve(i, j,'A') := X=i, Y=jはAであるか?とすると,
solve(i, j,'A') = (i, jから移動できるパターンのいずれかがBである ->必敗形で相手に手番を渡せる )
solve(i, j,'B') = (i, jから移動できるパターンの全てがAである -> どう動いても相手に必勝形で渡してしまう)
として遷移を書き, 10x10ぐらいで試すと,
B B A A A A A A A A
B B B A A A A A A A
A B B B A A A A A A
A A B B B A A A A A
A A A B B B A A A A
A A A A B B B A A A
A A A A A B B B A A
A A A A A A B B B A
A A A A A A A B B B
A A A A A A A A B B
となり, abs(X-Y) <= 1で勝敗が判定できることが分かる.
メモ
傾き-2,-1/2で移動できることが分かると簡単にプロットできるみたいだった.
実験すればできる問題だったが,証明力も磨きたい.
コード
#include "bits/stdc++.h" #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define RREP(i, x, n) for(int i = x; i >= n; i--) #define rrep(i, n) RREP(i,n,0) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define pb push_back using namespace std; using ll = long long; using P = pair<int,int>; const int mod=1e9+7,INF=1<<30; const double EPS=1e-12,PI=3.1415926535897932384626; const ll LINF=1LL<<60, lmod = 1e9+7; const int MAX_N = 100005; char res[101][101]; bool solve(int i,int j,char t){ if(res[i][j]!='X'){ return res[i][j] == t; } bool ret; if(t=='A'){ ret = false; REP(k,1,i/2+1) ret |= solve(i-2*k,j+k,'B'); REP(k,1,j/2+1) ret |= solve(i+k,j-2*k,'B'); if(ret) res[i][j] = 'A'; else res[i][j] = 'B'; }else{ ret = true; REP(k,1,i/2+1) ret &= solve(i-2*k,j+k,'A'); REP(k,1,j/2+1) ret &= solve(i+k,j-2*k,'A'); if(ret) res[i][j] = 'B'; else res[i][j] = 'A'; } return ret; } int main(){ ll X,Y; cin >> X >> Y; // rep(i,100) rep(j,100) res[i][j] = 'X'; // res[0][0] = res[0][1] = res[1][0] = res[1][1] = 'B'; // rep(i,10){ // rep(j,10){ // cout << (solve(i,j,'A') ? 'A' : 'B') << " "; // } // cout << "" << endl; // } if(abs(X-Y)>1) cout << "Alice" << endl; else cout << "Brown" << endl; return 0; }