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

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

ACL Contest 1 A - Reachable Towns (300 点)

えーーー、300 点!?

問題へのリンク

問題概要

二次元平面上に  N 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは  1, 2, \dots, N の順列となっている。

 k = 1, 2, \dots, N に対して、点  k から

  • 自分よりも x 座標と y 座標がともに大きな点
  • 自分よりも x 座標と y 座標がともに小さな点

への移動を繰り返して行くことのできる点の個数を求めよ。

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

この問題...たとえば下図だと、点 1 から点 2 へと直接行くことはできないが、点 3 を経由して互いに行き来することができる。こういうケースを扱うのが厄介そうに思えた。

f:id:drken1215:20200922232140p:plain

ひとつの重要な観察として、次のことがいえる。

  • 点 i から点 j へ行けるならば、点 j から点 i へも行ける
  • 点 i と点 j が互いに行き来可能で、点 j と点 k が互いに行き来可能ならば、点 i と点 k も互いに行き来可能である

よって、 N 点を「互いに行き来できる関係性」によってグループ分けすることが可能である。同一グループ内の点同士は互いに行き来可能であり、異なるグループの点同士は行き来不可能という具合になる。グループ分けといえば、Union-Find が使えそう。

解法 (1):平面走査 + Union-Find

この手の問題のもう一つの定石は、探索順序を上手に定めることだと思う。今回は x 座標が小さい順に見て行くことにしよう。x 座標が小さい順に見て行くメリットは、以下の通り。


今見ている点  (x, y) と過去の点  (x', y') とが行き来可能かどうかを判定するとき、 x' \lt x であることがわかっているので  y' \lt y かどうかを判定するだけでよい


よって、とりあえず以下のような実装でグループ分けすることができる。

UnionFind uf(N);
for (int i = 0; i < N; ++i) {
  for (int j = 0; j < i; ++j) {
    if (y[j] < y[i]) uf.merge(i, j);
  }
}

しかしこのままでは  O(N^{2}\alpha(N)) の計算量を要するため、改善が必要。

UnionFind の各グループの代表点のみ見る

 i 番目の点を  j = 0, 1, \dots, i-1 番目の点と行き来できるかどうかを調べるとき、すべての  j を調べる必要はない。具体的には

  • すでに形成されているグループのうち、1 点とのみ行き来可能かどうかを調べれば良い

と言える。その 1 点としては、 y 座標が最小の頂点を採用するのが都合がいい。そのような「各グループの代表点」を管理する方法としては、set を使ったり stack を使ったりする方法がある。

解答例 (1):set を用いた実装

計算量は  O(N \log N) となる。

#include <bits/stdc++.h>
using namespace std;

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

using pint = pair<int,int>; // y, id
int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i], --x[i], --y[i];
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) { return x[i] < x[j]; });

    UnionFind uf(N);
    set<pint> se;
    for (auto i : ids) {
        if (se.empty() || se.begin()->first > y[i]) {
            se.insert(pint(y[i], i));
        }
        else {
            auto it = se.begin();
            uf.merge(i, it->second);
            ++it;
            for (; it != se.end();) {
                if (it->first < y[i]) {
                    uf.merge(i, it->second);
                    it = se.erase(it);
                }
                else break;
            }
        }
    }
    for (int i = 0; i < N; ++i) cout << uf.size(i) << endl;
}

解答例 (2):stack を用いた実装

set を用いるよりも計算量は削減される。各グループの代表点のみを stack に残して行くイメージ。計算量は (ソートにバケットソートを用いれば)  O(N\alpha(N)) となる。下の実装では結局ソートをしているので  O(N \log N) となっている。

#include <bits/stdc++.h>
using namespace std;

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

using pint = pair<int,int>; // y, id
int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i], --x[i], --y[i];
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) { return x[i] < x[j]; });

    UnionFind uf(N);
    stack<pint> st;
    pint ymin = pint(1<<29, -1);
    for (auto i : ids) {
        if (ymin > pint(y[i], i)) {
            st.push(ymin);
            ymin = pint(y[i], i);
        }
        else {
            uf.merge(i, ymin.second);
            while (!st.empty() && st.top().first < y[i]) {
                uf.merge(i, st.top().second);
                st.pop();
            }
        }
    }
    for (int i = 0; i < N; ++i) cout << uf.size(i) << endl;
}

別解:O(N)

UnionFInd さえ使わない方法があるらしい!!!!!
よくよく考えると次の性質が言える


連結成分をなす点は、x 座標が連続値となる

 x_{i} \lt x_{j} \lt x_{k} で、 y_{i} \lt y_{k} となっているとする。このとき、 i, k は同じグループに属する。しかしこのとき、 y_{j} がどの位置にあったとしても、結局  i, j, k がすべて同じグループに属することが言えるのだ。

よって、結局グループ分けは下図みたいになるのだ。

f:id:drken1215:20200923032036p:plain

つまり、各連結成分は、その対角線がちょうど全体の対角線上にあるような感じになっている。ブロック対角行列みたいな形状になる。このことを利用すると、 O(N) で解くこともできる。

解答例 (3)

下の実装では愚直にソートしているので  O(N \log N) になっている。バケットソートを用いれば  O(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; }

using pint = pair<int,int>; // y, id
int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i], --x[i], --y[i];
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) { return x[i] < x[j]; });

    vector<int> res(N);
    int prex = 0, prey = N, miny = N;
    for (int i = 0; i < ids.size(); ++i) {
        chmin(miny, y[ids[i]]);
        if (prey - miny == i + 1 - prex) {
            for (int j = prex; j <= i; ++j) res[ids[j]] = prey - miny;
            prex = i + 1, prey = miny;
        }
    }
    for (auto v : res) cout << v << endl;
}