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]; } }