Codeforces ECR #068 : D. 1-2-K Game

この回もラスト2問が難しめだった。
http://codeforces.com/contest/1194/problem/D

問題

数値Nから始まる2人ターン制ゲームを考える。
各自のターンでは、数値を1,2,定数Kのいずれか減らすことができる。
ただし数値が負になる手は取れない。

互いに最適手を取るとき、勝者はどちらか。

解法

場合分けを細かくやっていく。
現在値がKなら先手必勝。
K未満なら良くある「1～3取るゲーム」の要領で、現在値が3の倍数でなければ、自分の手で3の倍数にできるので勝ち。
またKが3の倍数でないなら、各自の手は「mod 3で1か2しか動かせない」ので、同様に現在値が3の倍数となるように持ち込める。

以下、残りのケースであるKが3の倍数ではない場合が残る。
現在値をmod (K+1)でとり、K以外の3の倍数だと負け。Kを取ると相手が1とるのでmod (K+1)が変わらないし、それ以外だと「mod 3で1か2しか動かせない」のパターンになるため。

int T;
ll N,K;

/*
int memo[101];

int win(int cur) {
	if(memo[cur]>=0) return memo[cur];
	if(cur==0) return 0;
	if(win(cur-1)==0) return memo[cur]=1;
	if(cur>=2 && win(cur-2)==0) return memo[cur]=1;
	if(cur>=K && win(cur-K)==0) return memo[cur]=1;
	return memo[cur]=0;
}
*/
int win2(int cur) {
	if(cur==K) return 1;
	if(cur<=K) return cur%3!=0;
	if(K%3!=0) return cur%3!=0;
	cur%=(K+1);
	if(cur==K) return 1;
	if(cur%3==0) return 0;
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	/*
	for(K=3;K<=100;K++) {
		cout<<K<<" ";
		MINUS(memo);
		for(N=0;N<=100;N++) {
			cout<<(win(N)==win2(N));
		}
		cout<<endl;
	}
	*/
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		if(win2(N)) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
}

まとめ

シンプルな設定ながら、地味に場合分けが面倒臭い。