yukicoder : No.102 トランプを奪え

２問とも２人ゲームの問題。
http://yukicoder.me/problems/116

問題

トランプを同じスートごとに分けた最大４つの山がある。各山は1～13枚のいずれかの枚数のカードからなる。
ここで２人で以下のゲームを行う。

• ２人は交互にトランプを取り合う。その際、カードが残っている山を１つ選び、そこから１～３枚のカードを取る。
• 取ったカードは自分の手札となる。また、自分の手番で山を空にすると、ボーナスとして相手の手札を半分奪うことができる。
• 全部の山のカードがなくなったとき、手札の多い方が勝ちである。

４つの山のカード枚数N[0]～N[3]が与えられる。
最適手を取ったとき、先手と後手どちらが必勝か答えよ。

解法

４つの山のカード枚数と、片方の手持ちカードの枚数を保持して、カードの取り方を総当たりでメモ化再帰してもO(max(N)^5)で解ける。

ただこのゲーム、実は最後のカードを取ると相手のカードを半分奪えるので、最後のカードを取ったものが勝者となる。
そのため、手持ちのカード枚数の管理は実は不要でO(max(N)^4)で抑えられる。

また、Grundy(N[i])==N[i]%4となるNimと考えるともっと簡単に解ける。

int A[5],T;
int memo[14][14][14][14];

int win() {
	int i;
	int& ret=memo[A[0]][A[1]][A[2]][A[3]];
	
	if(A[0]+A[1]+A[2]+A[3]==0) return 0;
	if(ret==-1) {
		ret=0;
		int i,j;
		FOR(j,4) {
			for(i=1;i<=min(A[j],3);i++) {
				A[j]-=i;
				if(win()==0) ret=1;
				A[j]+=i;
			}
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>A[0]>>A[1]>>A[2]>>A[3];
	
	MINUS(memo);
	if(win()) cout<<"Taro"<<endl;
	else cout<<"Jiro"<<endl;
}

まとめ

最初愚直にO(max(N)^5)でやってしまった。