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