2020-11-02

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

AtCoder ABC-F AtCoder600点 Kruskal法二分探索グラフ計算幾何円最小全域木二次元平面上のN点の問題 Union-Find グラフのconnectivity 単調性に着目する密グラフ Greedy DFS BFS 連結成分黄色diff 全域木を考える浮動小数点型を扱う問題

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

問題概要

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