けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!!

問題概要

 xy 平面上に 2 直線  y=−100, y=100 で囲まれた通路がある。この通路の中の  −100 \lt x \lt 100 の部分に  N 本の大きさの無視できる釘が打たれており、 i 本目の釘の座標は  (x_{i}, y_{i}) である。

高橋くんは実数  r (0 \lt r \le 100) を 1 つ選び、半径  r の円を中心が  (−10^{9}, 0) に位置するように置く。その後、円を  (−10^{9}, 0) から  (10^{9}, 0) まで移動させる。

このとき、円は通路の境界や釘が円の内部に入らないような範囲で連続的に動かすことができるものとする。

円を  (10^{9},0) まで動かせるような最大の  r を求めてください。

制約

  •  1 \le N \le 100
  •  |x_{i}|, |y_{i}| \lt 100

解法(1):僕自身がやった解法 (二分探索)

問題見て条件反射で二分探索してしまった。つまり、ある実数  r が存在して、

  • 半径が  r より大きいと通過できない
  • 半径が  r 以下ならば通過できる

という風になっているはずなので、このような  r を二分探索で見つけたい。つまり、次の判定問題を解いた。


半径  x の円が通過できるかどうか?


これは次のようににして解けた。まず、次のような頂点数  N+2 のグラフを作った。

  • 直線  y = 100 と直線  y = -100 と、 N 個の合わせた  N+2 個のものを頂点集合にする (直線  y = 100 を頂点  s とし、直線  y = -100 を頂点  t とする)
  • これらの  N+2 個の頂点のうち、距離が  r 以下である 2 点間に辺を張っていく

このグラフで、2 頂点  s, t 間が連結であるとき、通過できない。非連結であるとき、通過できる。連結性の判定は、Union-Find でも、DFS でも、BFS でもできる。計算量は  R = 200 として、 O(N^{2} \log R) となる。

下の実装では、BFS を用いた。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    auto calc = [&](int i, int j) -> double {
        return sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]));
    };
    auto solve = [&](double d) -> bool {
        vector<int> dist(N+1, -1);
        queue<int> que;
        for (int v = 0; v < N; ++v) if (y[v] + d*2 >= 100) dist[v] = 1, que.push(v);
        while (!que.empty()) {
            int v = que.front();
            if (y[v] - d*2 <= -100) return true;
            que.pop();
            for (int nv = 0; nv < N; ++nv) {
                if (dist[nv] != -1) continue;
                if (calc(v, nv) <= d*2) {
                    dist[nv] = dist[v] + 1;
                    que.push(nv);
                }
            }
        }
        return false;
    };
    double left = 0.0, right = 100.0;
    for (int iter = 0; iter < 100; ++iter) {
        double x = (left + right) / 2;
        if (solve(x)) right = x;
        else left = x;
    }
    cout << fixed << setprecision(10) << left << endl;
}

解法 (2):実は二分探索要らない

解法 (1) を突き詰めると、実は二分探索不要で、次のようにすればよいことがわかる。


  •  N+2 個の頂点間を結ぶ辺のうち、長さの短いものから Greedy に繋いでいく
  • はじめて 2 頂点  s, t が連結になったときの辺の長さが求める答え

あらかじめ各辺を長さ順にソートして、Union-Find で効率よく管理しながら実装すると、計算量は  O(N^{2} \log N) となる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    auto calc = [&](int i, int j) -> double {
        return sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]));
    };
    
    using pint = pair<int,int>;
    using Edge = pair<double,pint>;
    vector<Edge> edges;
    int s = N, t = N+1;
    for (int i = 0; i < N; ++i) {
        edges.push_back(Edge(100.0-y[i], pint(s,i)));
        edges.push_back(Edge(y[i]+100.0, pint(t,i)));
        for (int j = i+1; j < N; ++j) edges.push_back(Edge(calc(i, j), pint(i, j)));
    }
    sort(edges.begin(), edges.end());
    UnionFind uf(N+2);
    double res = 0.0;
    for (auto e : edges) {
        uf.merge(e.second.first, e.second.second);
        if (uf.issame(s, t)) {
            res = e.first / 2;
            break;
        }
    }
    cout << fixed << setprecision(10) << res << endl;
}

解法 (3):最小全域木を Prim 法で求めることで計算量改善

解法 (2) の手続きを振り返ってみよう。解法 (2) の手続きは「最小全域木を求める Kruskal 法」にほとんど等しいことがわかる。

ここでさらに、解法 (2) の手続きにおいて、2 頂点  u, v を繋ごうとするとき、それらがすでに同一の連結成分内になるならば、繋ぐ必要がないことにも注意する。よって、そのような場合は繋がないように修正したとき、解法 (2) の手続きは、完全に Kruskal 法の手続きと一致する。

よって、今回の問題は次のようにして解けることが言える。


  •  N+2 頂点のグラフの最小全域木を考える
  • 2 頂点  s, t を結ぶパス上の辺の長さの最大値が答え

よって、最小全域木を求められればよいことになる。蜜グラフの最小全域木は、「単純な Prim 法」によって  O(N^{2}) でできる。

よって、今回の問題自体も  O(N^{2}) で解ける!!!