TopCoder SRM 692 Div1 Easy: OrderOfTheHats
解法
二分探索+全探索+BFS
コード
#include <bits/stdc++.h> using namespace std; class HardProof { int N; bool check(const vector<int> &D, int minCost, int maxCost) { vector<vector<bool>> g(N, vector<bool>(N, false)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { g[i][j] = minCost <= D[i * N + j] && D[i * N + j] <= maxCost; } g[i][i] = true; } // BFS で0から行ける場所、0に行ける場所をそれぞれtrueにする queue<int> que; for (int i = 0; i < N; ++i) if (g[0][i]) que.push(i); while (!que.empty()) { int i = que.front(); que.pop(); for (int j = 0; j < N; ++j) if (g[i][j] && !g[0][j]) { g[0][j] = true; que.push(j); } } for (int i = 0; i < N; ++i) if (g[i][0]) que.push(i); while (!que.empty()) { int i = que.front(); que.pop(); for (int j = 0; j < N; ++j) if (g[j][i] && !g[j][0]) { g[j][0] = true; que.push(j); } } // すべての場所が0から行けるのかチェック for (int i = 0; i < N; ++i) if (!g[0][i] || !g[i][0]) return false; return true; } public: int minimumCost(vector<int> D) { N = sqrt(D.size()); set<int> costs; for (int i : D) costs.insert(i); int high = 1e8; int low = -1; while (high - low > 1) { int mid = (high + low) / 2; bool ok = false; for (int minCost : costs) { int maxCost = minCost + mid; if (check(D, minCost, maxCost)) { ok = true; break; } } if (ok) { high = mid; } else { low = mid; } } return high; } };