1230-Nim

問題概要

S個の石から1〜m[turn%(2*n)]個の石を互いにとっていくゲームをする．
最善を付くした時にどちらが勝つかを求めよ

解法

数は減るのでループが発生しないのでmin-max法をメモ化する
計算量はO(NS)

実装(C++)

#include <iostream>
#include <cstring>
using namespace std;
int n,s,m[20];
int dp[2<<14][30];
int solve(int remain,int turn){
	if(remain<=1){
		if(turn%2==0)return 0;
		else return 1;
	}else{
		int ans=0;
		if(dp[remain][turn%n]>=0)return dp[remain][turn%n];
		if(turn%2==0){
			for(int i=1;i<=m[turn%n];i++){
				ans=max(ans,solve(remain-i,turn+1));
			}
		}else{
			ans=1;
			for(int i=1;i<=m[turn%n];i++){
				ans=min(ans,solve(remain-i,turn+1));
			}
		}
		return dp[remain][turn%n]=ans;
	}
}
int main() {
	while(cin>>n,n){
		cin>>s;
		for(int i=0;i<2*n;i++){
			cin>>m[i];
		}
		n*=2;
		memset(dp,-1,sizeof(dp));
		cout<<solve(s,0)<<endl;
	}
	return 0;
}