TopCoder SRM 419 Div1 Medium NimForK

問題

k人がn個の石を使って次のようなゲームをする。

• k人は時計回りに並び、1番の人から時計回りに順にターンをまわす。
• ターンの人は山から石を取る。このとき取れる石の個数は下の条件を満たす必要がある。
• 山の石がなくなったときゲーム終了。最後に石を取った人が勝ち。
• 山に石があるのに、それ以上石を取れなくなったときは、勝者なしでゲーム終了。

山の石がi個のときに取れる石の個数はmoves[i][]のどれか。

それぞれの人は以下の戦略で石を取る。

• 他の人は全員自分と同じ戦略を取っているとする。
• 他の人がどのように石を取っても自分が勝つ手があるときは、その手を選択する。
• 自分が勝つ確率が0でない手があるとき、その手を選ぶ。それが複数ある場合、その中から一つをランダムで選ぶ。
• 自分が負ける手しかないとき、その手を選ぶ。複数ある場合はその中からランダムで一つ選ぶ。

moves[i][]が与えられたとき、勝つ確率がある人の番号を全て出力せよ。

制約条件

n≦50
k≦20

方針

動的計画法による。
dp[i][j]を、山に石がi個残っていて、現在の手番がjの人のときに、
勝てる確率のある人の集合とする。

これを更新していくようなDPをすればいい。
一つ注意する必要があるのは、
「i番目の人が必ず勝つ」という状態と「i番目の人のみ、勝つ確率がある」という状態を区別する必要があるということ。
後者は、「i番目の人が勝つ、または引き分け」という状態である。

ソースコード

int k;
vector<vi> ms;
int dp[100][100];
int rec(int n, int cur){
	int &res = dp[n][cur];
	if(res >= 0) return res;
	
	if(n == 0){
		int w = (cur + k - 1) % k;
		return res = 1 << w;
	}
	
	res = 1 << k;
	bool f = 1;
	rep(i, ms[n - 1].size()){
		int tmp = rec(n - ms[n - 1][i], (cur + 1) % k);
		if(tmp == 1 << cur) return res = 1 << cur;
		if(tmp & 1 << cur){
			if(res & 1 << cur) res |= tmp;
			else res = tmp;
		}
		else{
			if(!(res & 1 << cur)){
				if(f) res = tmp;
				else res |= tmp;
			}
		}
		f = 0;
	}
	if(res < 0) res = 0;
	return res;
}

class NimForK {
	public:
	vector <int> winners(int n, int k, vector <string> moves) 
	{
		rep(i, 100) rep(j, 100) dp[i][j] = -1;
		
		ms.clear();
		ms.resize(n);
		rep(i, n){
			stringstream ss(moves[i]);
			int t;
			while(ss >> t) ms[i].pb(t);
		}
		::k = k;
		
		int ans = rec(n, 0);
		vi v;
		rep(i, k) if(ans & 1 << i) v.pb(i + 1);
		return v;
	}
};