AOJ1230 Nim

問題リンク Nim

• 概要

Nimというゲームをやる。石の山から石を1〜4個交代でとっていき、最後の1個を取った人が負けである。
ただ、今回のNimは少しルールが違う。
まず、チームでプレイする。1チームはN人であり、全部で2N人でプレイする。石を取る順番は味方チームの1人目、相手チームの1人目、味方チームの2人目...とする。
そして、石を取る個数の上限 Mi が人によってバラバラである。
今石の数がS個であるとき、味方のチームが必ず勝つ戦略は存在するかを調べる。存在するなら1, そうでないならば0と答えよ
N<=10
S<=2^13
Mi<=16

• 解法

DPで解きます。
dp[i][j]: 残りの石の個数が j のときに i のターンが来た時に最善の戦略を取った時、勝つか負けるか
dp[i][1] は残りの石が1個しかないので必ず負けます。
dp[i][j] をどう埋めるかですが、この人が1〜m個の石を取れるとき、dp[i+1][j-k] (1<=k<=m)を見ていき、この中に1つでもfalse (=負ける)があれば、この人は k 個の石を取ることで必ず勝つことができます。それ以外なら負けます。
このdpの表を石の残り数が少ない方から埋めていき、dp[0][S]がtrueならば必ず勝つ戦略があると分かります。

• ソース

import java.util.Scanner;

//Nim
public class AOJ1230 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			int s = sc.nextInt();
			int[] m = new int[2*n];
			for(int i=0;i<2*n;i++)m[i]=sc.nextInt();
			boolean[][] dp = new boolean[2*n][s+1];
			for(int j=2;j<=s;j++)for(int i=0;i<2*n;i++){
				boolean w = false;
				for(int p=1;p<=m[i];p++){
					if(j-p<=0)break;
					if(!dp[(i+1)%(2*n)][j-p])w=true;
				}
				dp[i][j] = w;
			}
			System.out.println(dp[0][s]?1:0);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1230().run();
	}
}