読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 511 Div1 Medium: FiveHundredEleven

解法

ゲーム木的な考え方で深さ優先探索する。実は今までどのカードを取ったかを記録しておく必要はない。現状のビットを維持できる(現状のビットに影響のないカードを取ることができる)なら511を作って負けることはないので、ビットを増やしてしまうカードを取る際に負けないかどうかだけを気にすれば良い。

コード

import java.util.Arrays;

public class FiveHundredEleven {
	private int N;
	private int[][] dp;
	private int[] cards;
	private final int WIN = 1;
	private final int LOSE = 0;

	public String theWinner(int[] c) {
		N = c.length;
		this.cards = c;
		dp = new int[512][N + 1];
		for (int i = 0; i < 512; i++) {
			Arrays.fill(dp[i], -1);
		}

		if (dfs(0, 0) == WIN) {
			return "Fox Ciel";
		} else {
			return "Toastman";
		}
	}

	private int dfs(int bit, int step) {
		if (bit == 511) {
			// 自分のターンにbit=511で回ってきたということは、
			// 直前の相手が511を作っているので、相手の負けである
			return WIN;
		}

		if (step == N) {
			// 0起点でNターン目にはカードが残っていないので負けである
			return LOSE;
		}

		// メモ化再帰
		if (dp[bit][step] != -1) {
			return dp[bit][step];
		}
		dp[bit][step] = LOSE;

		int noEffect = 0;// bitを現状維持できるカードの枚数
		for (int x = 0; x < N; x++) {
			if ((bit | cards[x]) == bit) {
				noEffect++;
			}
		}

		if (step < noEffect && dfs(bit, step + 1) == LOSE) {
			// 現状維持できて、かつ、敵が次のターンで負け確定するなら勝てる
			dp[bit][step] = WIN;
		}

		for (int x = 0; x < N; x++) {
			// 現状維持できなくてもnextBitで勝てるなら勝てる
			int nextBit = bit | cards[x];
			if (nextBit != bit && dfs(nextBit, step + 1) == LOSE) {
				dp[bit][step] = WIN;
			}
		}
		return dp[bit][step];

	}
}