ARC 046 B - 石取り大作戦
問題概要
プレイヤーが交互に1個以上の石をとる. 最後に石をとったプレイヤーの勝利. 先手はA個まで, 後手はB個まで石をとることができる. 最適に行動したときどちらが勝利するか.
解法
まずN<=Aの時は先手がN個とって勝ち.
次に, 二人のプレイヤーが合計A+1をとることを考える. 先手がx(<=A)をとったなら, 後手はA+1-xをとるようにする. このような時, NがもしA+1の倍数なら, A+1-xをとるほうが必ず勝てる. これは後手が2人の合計を調整することで相手が石をとりきることができる, 自分が石をとりきることができる番を作っているから.
これを踏まえて, N<=A以外の場合だが, AとBが一致しているときとしていない時で場合分けができる.
一致しているとき, NがA+1の倍数なら合計A+1をとるように後手が調整できるのでBが勝つことができる. NがA+1の倍数でないとき, 一番はじめの手で先手がNがA+1の倍数になるように石の総数をちょうせいできるので, そのあとは後手が取った石の数に対して先手が石の数を調整していくことができるので, 先手が勝つことになる.
一致していないときで, A>Bのとき, 先手は1つ石をとった後, N-1>A-1>=Bとなるので, 後手の1ターン目では試合を終わらすことができず, そのあとは先手が後手のとった石の数から調整して残りの石がB+1の倍数残るようにしていけば, 勝つことができる(たぶん).
A<Bのときは, 後手が残りの石をA+1の倍数になるように調整していけば最後に後手が勝てるときがくる(たぶん).
ミス
ゲームは難しいね.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; int main(void){ int n, a, b; cin >> n >> a >> b; if(n <= a){ printf("Takahashi\n"); }else{ if(a == b){ // n = a + 1 なら必ず後手勝利. つまり, 先手が x を出したなら, 後手は a + 1 - x を出すようにすればいい. // 違うなら, 先手が上の状況を相手に与えられる. if(n % (a + 1) == 0) printf("Aoki\n"); else printf("Takahashi\n"); }else{ // 多いほうが勝ち // 合計で a + 1 とるように選ぶのを 多いほうがやればいい. if(a > b) printf("Takahashi\n"); else printf("Aoki\n"); } } return 0; }