AtCoder ACL contest 1 A問題 Reachable Towns

問題文

$2$次元平面上に$N$個の街があります。$i$個目の街の座標は $(x_i,y_i)$です。ここで、
$(x_1, x_2, \dots ,x_N)$と$y_1, y_2, \dots, y_N$は、ともに
$(1, 2, \dots, N)$の順列となっています。

各$k=1,2,\dots,N$について、以下の問いに答える。

最初街$k$にいて、今いる街よりも「$x,y$座標がともに小さい街」か「$x,y$座標がともに大きい街」に移動することを好きな回数繰り返すことができる。
到達可能な街は街$k$を含めて何種類あるか。

解答1

頂点$(x_i, y_i)$、$(x_j, y_j)$$(i \neq j)$について、「$x_i < x_j$ かつ $y_i < y_j$」または「$x_i > x_j$かつ$y_i > y_j$」となるなら無向辺を張る。
その後、各頂点$k$の連結成分を答えればいい。

\\ Union-Find
dsu d(n);
for(int i = 0; i < n; ++i) {
    for(int j = 0; j < i; ++j) {
        if(x[i] > x[j] && y[i] > y[j]) d.merge(i, j);
        if(x[i] < x[j] && y[i] < y[j]) d.merge(i, j);
    }
}

しかし、上記の通りだと計算量が$O(N^2)$になってしまう。
それに、上記のコードでは、すでに同じ連結成分に属している頂点の組を何回もマージすることになり、効率が悪い。

そこで、まず頂点をソートして、頂点を$x$座標が小さい順に見ていく。
すると、すでにみた頂点集合のうち今見ている頂点より$y$座標が小さい頂点と連結させればいいので、上のコードは以下のように簡略化できる

\\ Union-Find
dsu d(n);
for(int i = 0; i < n; ++i) {
    for(int j = 0; j < i; ++j) {
        if(y[i] > y[i]) d.merge(i, j);
    }
}

上のコードの、頂点を連結させる回数はもっと減らすことができる。つまり、すでにみた頂点の集合について、各連結成分の内$y$座標が最も小さいものだけを見て、いま見ている頂点より$y$座標が小さかったら連結させればいいことがわかる。
なので、そのような頂点をsetで管理して、その都度取り出すようにする。
以上で、mergeの回数をならしで$O(N)$回に減らせる。
(証明はわからない、、)

各連結成分で$y$座標が最も小さいものの管理はstackを使ってもできます。
注)atcoder-libraryを使っています

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

#include <cassert>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < (n); ++(i))
using namespace std;

// setmax, setmin, vectors関数は、kimiyukiさんの記事のものを使っています
// kimiyukiさんありがとうございます
// https://kimiyuki.net/writeup/algo/etc/icpc-2016-domestic-d/
template <class T>
void setmax(T &a, T const &b) {
    if (a < b) a = b;
}

template <class T>
void setmin(T &a, T const &b) {
    if (a > b) a = b;
}

template <typename T, typename X>
auto vectors(T a, X x) { return vector<T>(x, a); }

template <typename T, typename X, typename Y, typename... Zs>
auto vectors(T a, X x, Y y, Zs... zs) {
    auto cont = vectors(a, y, zs...);
    return vector<decltype(cont)>(x, cont);
}

using namespace atcoder;
const int INF = (int)1e9;

int main() {
    int N;
    cin >> N;
    vector<tuple<int, int, int>> xyi(N);
    repeat(i, N) {
        int x, y;
        cin >> x >> y;
        xyi[i] = make_tuple(x, y, i);
    }

    sort(xyi.begin(), xyi.end());
    vector<int> res(N);
    dsu d(N);
    // first := y座標のmin, second := 元のインデックス
    set<pair<int, int>> tail;
    for (int i = 0; i < N; ++i) {
        int y = get<1>(xyi[i]);
        int ymin = y;
        int id = get<2>(xyi[i]);
        auto it = tail.upper_bound({y-1, INF});
        // [tail.begin(), it)をマージ
        auto ptr = tail.begin();
        while (ptr != it) {
            int py = ptr->first;
            int par = ptr->second;
            setmin(ymin, py);
            d.merge(par, id);
            tail.erase(ptr++);
        }
        tail.emplace(ymin, id);
    }

    for (int i = 0; i < N; ++i) {
        int id = get<2>(xyi[i]);
        res[id] = d.size(id);
    }

    for (int i = 0; i < N; ++i) {
        cout << res[i] << endl;
    }
    return 0;
}

解放2(未証明、実装のみ、、、)

頂点をソートして$x$座標が小さい順に見ます。

頂点$i$と頂点$i+1$について、「$y_1, \dots, y_i$が$(N,\dots, N - i + 1)$の順列」であるときのみ非連結であり、そうでないとき必ず連結になる

ことがわかります（あとで証明かなんかできたらいいな、、）

なので、その通りに判定します

注)atcoder-libraryを使っています

#include <algorithm>

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

#include <cassert>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < (n); ++(i))
using namespace std;


// setmax, setmin, vectors関数は、kimiyukiさんの記事のものを使っています
// kimiyukiさんありがとうございます
// https://kimiyuki.net/writeup/algo/etc/icpc-2016-domestic-d/
template <class T>
void setmax(T &a, T const &b) {
    if (a < b) a = b;
}

template <class T>
void setmin(T &a, T const &b) {
    if (a > b) a = b;
}

template <typename T, typename X>
auto vectors(T a, X x) { return vector<T>(x, a); }

template <typename T, typename X, typename Y, typename... Zs>
auto vectors(T a, X x, Y y, Zs... zs) {
    auto cont = vectors(a, y, zs...);
    return vector<decltype(cont)>(x, cont);
}

int main() {
    int N;
    cin >> N;
    vector<tuple<int, int, int>> xyi(N);
    repeat(i, N) {
        int x, y;
        cin >> x >> y;
        xyi[i] = make_tuple(x, y, i);
    }

    sort(xyi.begin(), xyi.end());

    atcoder::dsu d(N);
    int ymin = int(1e9);
    for (int i = 0; i < N; ++i) {
        if (i > 0) {
            // i と i-1が連結しているか
            if (!(ymin == N - i + 1)) d.merge(i, i - 1);
        }
        int y = get<1>(xyi[i]);
        setmin(ymin, y);
    }

    vector<int> res(N);
    for (int i = 0; i < N; ++i) {
        int id = get<2>(xyi[i]);
        res[id] = d.size(i);
    }

    for (int i = 0; i < N; ++i) {
        cout << res[i] << endl;
    }
    return 0;
}