Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@takoyakimaster65

AtCoder ACL contest 1 A問題 Reachable Towns

Last updated at Posted at 2020-09-21

問題文

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?