TopCoder SRM606: EllysCandyGame
dp[ビット表現] = {-1,0,1} でメモ付き探索できそうに見えるが、取る順番によって盤面の状態が変わるので実はできない。
よく考えると、キャンディの個数は 10 個以下 で、わざわざメモらなくても高々 10! の計算量になるため、ただのゲーム木上の全探索で十分間に合う。
public class EllysCandyGame { int dfs(int[] sweets, int taked, int sum1, int sum2) { int n = sweets.Length; int val = 999; for (int i = 0; i < n; i++) { if (sweets[i] == 0) continue; if ((taked & (1 << i)) != 0) continue; int ratio = 1; if (i - 1 >= 0 && ((1 << (i - 1)) & taked) != 0) ratio *= 2; if (i + 1 < n && ((1 << (i + 1)) & taked) != 0) ratio *= 2; val = Math.Min(val, -dfs(sweets, taked | (1 << i), sum2, sum1 + sweets[i] * ratio)); } if (val == 999) { val = 0; if (sum1 < sum2) val = 1; if (sum1 > sum2) val = -1; } return val; } public string getWinner(int[] sweets) { int ans = dfs(sweets, 0, 0, 0); if (ans == 1) return "Kris"; if (ans == -1) return "Elly"; return "Draw"; } }
あらためて考えてみたら、dp[ビット表現] = 自分が取れるスコア - 相手が取れるスコア でメモ付き探索できた。
public class EllysCandyGame { int?[] memo = new int?[1 << 10]; int dfs(int[] sweets, int taked) { int n = sweets.Length; if (!memo[taked].HasValue) { int val = int.MinValue; for (int i = 0; i < n; i++) { if (sweets[i] == 0) continue; if ((taked & (1 << i)) != 0) continue; int ratio = 1; if (i - 1 >= 0 && ((1 << (i - 1)) & taked) != 0) ratio *= 2; if (i + 1 < n && ((1 << (i + 1)) & taked) != 0) ratio *= 2; val = Math.Max(val, -dfs(sweets, taked | (1 << i)) + sweets[i] * ratio); } if (val == int.MinValue) { val = 0; } memo[taked] = val; } return memo[taked].Value; } public string getWinner(int[] sweets) { int ans = dfs(sweets, 0); if (ans < 0) return "Kris"; if (ans > 0) return "Elly"; return "Draw"; } }