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