TopCoder SRM579: TravellingPurchasingMan

「現在の位置」「買い物をした店のbit表現」 = 最小の時間
で動的計画法を行う。制約では何気に M <= 16 となっており、これで十分間に合う。

各店間での移動にかかる時間は事前に Warshall-Folyd で求めておく。

今回は PriorityQueue の実装も兼ねて、動的計画法ではなくダイクストラで解いた。想定解法というわけでもなく動的計画法より計算量が log の分増えるので時間ギリギリ（最大 1.7s) でなんとか通った。無駄なデータを極力キューに入れないような手回しをしないと TLE になる。

public class TravellingPurchasingMan {
    static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = newValue; }

    const int INF = 1 << 29;
    int N, M;
    int[,] d;
    Store[] stores;

    struct Store {
        public int from, to, duration;
    }

    struct State {
        public int visited, pos, time;
    }

    static public int BitCount(long x) {
        int bitCount = 0;
        for (; x != 0; x = x & (x - 1)) bitCount++;
        return bitCount;
    }

    public int maxStores(int N, string[] interestingStores, string[] roads) {
        this.N = N;
        this.M = interestingStores.Count();
        this.d = new int[N, N];
        this.stores = interestingStores
            .Select(s => s.Split().Select(int.Parse).ToArray())
            .Select(a =>
                new Store {
                    from = a[0],
                    to = a[1],
                    duration = a[2]
                }
            ).ToArray();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i, j] = INF;
            }
            d[i, i] = 0;
        }
        foreach (var road in roads) {
            var a = road.Split().Select(int.Parse).ToArray();
            int from = a[0];
            int to = a[1];
            int distance = a[2];
            d[from, to] = distance;
            d[to, from] = distance;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    UpdateMin(ref d[j, k], d[j, i] + d[i, k]);
                }
            }
        }

        var qu = new PriorityQueue<State>((s1, s2) => -s1.time.CompareTo(s2.time));
        int?[,] minTime = new int?[M, 1 << M];
        int ans = 0;

        for (int i = 0; i < M; i++) {
            int time = Math.Max(d[i, N - 1], stores[i].from);
            if (time <= stores[i].to)
                qu.Enqueue(new State { pos = i, visited = (1 << i), time = time + stores[i].duration });
        }

        while (qu.Any()) {
            State now = qu.Dequeue();
            ans = Math.Max(ans, BitCount(now.visited));
            for (int j = 0; j < M; j++) {
                if ((now.visited & (1 << j)) != 0) continue;
                int newTime = Math.Max(now.time + d[now.pos, j], stores[j].from);
                if (newTime <= stores[j].to) {
                    newTime += stores[j].duration;
                    var newState = new State { pos = j, visited = now.visited | (1 << j), time = newTime };
                    if (minTime[newState.pos, newState.visited].HasValue &&
                        minTime[newState.pos, newState.visited] <= newTime) continue;
                    minTime[newState.pos, newState.visited] = newTime;
                    qu.Enqueue(newState);
                }
            }
        }

        return ans;
    }
}

メモ付き探索でも解いてみたけど、どう考えても非再帰で解いたほうがわかりやすい。

public class TravellingPurchasingMan {

    static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = newValue; }

    const int INF = 1 << 29;
    int N, M;
    int[,] d;
    int?[,] memo;
    Store[] stores;

    struct Store {
        public int from, to, duration;
    }

    public int dfs(int pos, int remain = 0) {
        Store store = stores[pos];
        if (remain == (1 << pos)) {
            int start = Math.Max(store.from, d[pos, N - 1]);
            if (start > store.to) return INF;
            return start + store.duration;
        }

        if (!memo[pos, remain].HasValue) {
            int val = INF;
            for (int i = 0; i < M; i++) {
                if ((remain & (1 << i)) == 0) continue;
                if (i == pos) continue;
                if (d[pos, i] == INF) continue;
                int minTime = dfs(i, remain ^ (1 << pos)) + d[pos, i];
                if (minTime > store.to) continue;
                int sub = Math.Max(minTime, store.from) + store.duration;
                UpdateMin(ref val, sub);
            }
            memo[pos, remain] = val;
        }
        return memo[pos, remain].Value;
    }


    static public int BitCount(long x) {
        int bitCount = 0;
        for (; x != 0; x = x & (x - 1)) bitCount++;
        return bitCount;
    }

    public int maxStores(int N, string[] interestingStores, string[] roads) {
        this.N = N;
        this.M = interestingStores.Count();
        this.d = new int[N, N];
        this.stores = interestingStores
            .Select(s => s.Split().Select(int.Parse).ToArray())
            .Select(a =>
                new Store {
                    from = a[0],
                    to = a[1],
                    duration = a[2]
                }
            ).ToArray();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i, j] = INF;
            }
            d[i, i] = 0;
        }
        foreach (var road in roads) {
            var a = road.Split().Select(int.Parse).ToArray();
            int from = a[0];
            int to = a[1];
            int distance = a[2];
            d[from, to] = distance;
            d[to, from] = distance;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    UpdateMin(ref d[j, k], d[j, i] + d[i, k]);
                }
            }
        }

        memo = new int?[M, 1 << M];

        int ans = 0;

        for (int i = 1; i < (1 << M); i++) {
            int bitNum = BitCount(i);
            if (bitNum <= ans) continue;
            for (int j = 0; j < M; j++) {
                if (((1 << j) & i) != 0 && dfs(j, i) < INF) {
                    ans = bitNum;
                    break;
                }
            }
        }

        return ans;
    }
}