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