TopCoder SRM 588: KeyDungeonDiv1

問題文

「ドアの使用状況」×「赤い鍵の個数」×「緑色の鍵の個数」でメモ付き探索で通るけど、「ドアの使用状況」×「赤い鍵の個数」だけでも通る。

しかし、前者はたまたまメモリが足りただけ、後者はたまたま上手くいくだけ（証明できない）で想定解法ではない。

想定解法は、白い鍵のそのまま状態として持つのではなく、その場で「赤い鍵」と「緑色の鍵」へ変換することで状態を減らして、DP や メモ付き探索を行う。

想定解法ではないコード

public class KeyDungeonDiv1 {
    public struct Door
    {
        public int doorR, doorG, roomR, roomG, roomW;
    }

    int?[,,] memo;

    public int dfs(List<Door> doors, int used, int r, int g, int w) {
        int ret = r + g + w;
        if (used == (1 << doors.Count) - 1) return ret;

        var key = new[] { used, r, g };
        var memoise = (int?)memo.GetValue(key);
        if (memoise.HasValue) return memoise.Value;

        for (int i = 0; i < doors.Count; i++) {
            if (((1 << i) & used) != 0) continue;
            int needW = Math.Max(0, doors[i].doorR - r) + Math.Max(0, doors[i].doorG - g);
            if (needW > w) continue;
            int nr = Math.Max(r - doors[i].doorR, 0) + doors[i].roomR;
            int ng = Math.Max(g - doors[i].doorG, 0) + doors[i].roomG;
            int nw = w - needW + doors[i].roomW;
            ret = Math.Max(ret, dfs(doors, used | (1 << i), nr, ng, nw));
        }
        memo.SetValue(ret, key);
        return ret;
    }

    public int maxKeys(int[] doorR, int[] doorG, int[] roomR, int[] roomG, int[] roomW, int[] keys) {
        int N = doorR.Length;
        List<Door> doors = new List<Door>();
        for (int i = 0; i < N; i++) {
            doors.Add(new Door() {
                doorG = doorG[i],
                doorR = doorR[i],
                roomR = roomR[i],
                roomG = roomG[i],
                roomW = roomW[i],
            });
        }
        int[, ,] dd = new int[1 << 13, 122, 122];
        memo = new int?[1 << 13, 122, 122];
        int v = dd.Length;
        return dfs(doors, 0, keys[0], keys[1], keys[2]);
    }
}

想定解法のコード

こちらのほうは状態数が意外と多くなるため、Array.GetValue/SetValue を使うと遅すぎて TLE だった。残念ながらこれらの関数は使わないほうが良さそうだ。

public class KeyDungeonDiv1 {
    public struct Door {
        public int doorR, doorG, roomR, roomG, roomW;
    }

    int?[,] memo;
    public int dfs(List<Door> doors, int used, int r, int g) {
        int ret = r + g;
        if (used == (1 << doors.Count) - 1) return ret;

        var memoise = memo[used, r];
        if (memoise.HasValue) return memoise.Value;

        for (int i = 0; i < doors.Count; i++) {
            if (((1 << i) & used) != 0) continue;
            if (r < doors[i].doorR || g < doors[i].doorG) continue;
            int nr = r - doors[i].doorR + doors[i].roomR;
            int ng = g - doors[i].doorG + doors[i].roomG;
            for (int redFromWhite = 0; redFromWhite <= doors[i].roomW; redFromWhite++) {
                ret = Math.Max(ret, dfs(doors, used | (1 << i), nr + redFromWhite, ng + (doors[i].roomW - redFromWhite)));
            }
        }

        memo[used, r] = ret;
        return ret;
    }

    public int maxKeys(int[] doorR, int[] doorG, int[] roomR, int[] roomG, int[] roomW, int[] keys) {
        int N = doorR.Length;
        List<Door> doors = new List<Door>();
        for (int i = 0; i < N; i++) {
            doors.Add(new Door() {
                doorG = doorG[i],
                doorR = doorR[i],
                roomR = roomR[i],
                roomG = roomG[i],
                roomW = roomW[i],
            });
        }
        memo = new int?[1 << 12, 260];
        int ans = keys.Sum();
        int white = keys[2];
        for (int r = 0; r <= white; r++) {
            ans = Math.Max(ans, dfs(doors, 0, keys[0] + r, keys[1] + white - r));
        }
        return ans;
    }