競プロ日記

https://atcoder.jp/contests/abc131/submissions/7223770

#include <bits/stdc++.h>
#define rep(i, n)     for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n)    for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n)    for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n)   for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v)  for (auto &&V : v)
#define all(x)        (x).begin(), (x).end()
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = 1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;

class UnionFind {
  std::vector parent_;

  public:
  UnionFind(int size_num) : parent_(size_num, -1) {}
  int find(int x) {
    if (parent_[x] < 0) return x;
    return parent_[x] = find(parent_[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (parent_[x] > parent_[y]) std::swap(x, y);
    parent_[x] += parent_[y];
    parent_[y]  = x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  int size(int x) {
    return -parent_[find(x)];
  }
};

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n;
  cin >> n;
  vector x(n), y(n);
  rep (i, n) cin >> x[i] >> y[i];
  UnionFind uf(100001);
  unordered_map<int, int> firstx;
  rep (i, n) {
    if (firstx.find(y[i]) == firstx.end()) {
      firstx[y[i]] = x[i];
    }
    uf.unite(firstx[y[i]], x[i]);
  }
  unordered_set checkedy;
  lint cnt = 0;
  rep (i, n) {
    if (checkedy.find(y[i]) == checkedy.end()) {
      cnt += uf.size(x[i]) - 1;
      checkedy.insert(y[i]);
    } else {
      --cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}

ABCの最終問題は3回に1回くらいの割合でほぼ自力で解けるイメージなのだが、最近は難しい問題が続いていたのと、行列とかセグメントツリーとかの実装に時間を費やしたおかげで、自力で解けた！という感覚が久しぶり。
1回しか使ったことないのにUnionFind使えそうだなって気づけたのは成長感じる。
前回はインデックスを保存していたので、値に対してもUnionFindを使えると気づくのに少し手間取ったが、気づけば方向性の決定はすぐだった。

今回は実は完全に自力ではなく、WAしてからテストケースをチラ見してACした。
int型じゃ答えが入り切らなかった・・・。
ここ2,3日だけでこのミス3回くらいした気がする、マジで気をつけよう。

自力で解けた基本的には書くことがないのだが、他の解説と本質は同じ(だと思う)だが見かけの考え方が書かれてなくて後でどう考えたんだろうってなりそうなのでメモ。
二部グラフなんて二色で塗れますかしか知らないので思いつくはずもない。

考え方

x軸を主にしてもy軸を主にしても良いが、ここではx軸を主にする。

とりうるy座標の値全てに対して、そのy座標を持つ点のx座標の集合を作成する。
ある点Pと同じy座標に新たに点を追加することを考えた場合、その点Pのx座標[Px]が含まれる全ての集合の、[Px]以外の全てのx座標[Xi]を持つ点[Xi, Py]が追加される。
全てのy軸に対してこの操作を行うと、点Pを点に持つ長方形を全て作成できる。
※ここでは追加したい点に既に点があることは考えない。

すなわち、x座標が与えられたときに、そのx座標が属している集合を全て求められれば良い。
ここで、点を追加する際に、点Pのy座標以外のy座標は考えなくても良いことに気づくので、x座標が含まれる集合はy座標ごとに保持する必要はなく、集合間に重複する要素がある場合は結合しても良いことが分かる。
結合することでO(n*yMAX)からO(n)になって間に合う。


なぜ結合して良いのか、なぜy軸についても同じ操作をしなくて良いのか、感覚的にあやふやになりそうなので僅かに理論的な説明。

まず、なぜy軸についても同じ操作をしなくて良いのかについて。
点を追加しきった最終的な形を見ると、長方形を成している4つの点と、同じx座標かy座標を持つ点が3つ以上無く、2つ以下で独立している点に分けられる。
3つの点から長方形を作るパターンでは、左上・右上・左下・右下のどの点が欠けている場合でも、上記の方法で正しく長方形を作成することができる。
長方形は3つの点からしか作ることができないので、x軸かy軸いずれかを主にして考えるだけで全ての長方形を作成することができる。
2つ以下で独立した場合については、どちらを主にして考えても長方形を作ることができないので、どちらで考えても良い(どちらでも考える必要がない)。
よって、どちらか片方のみについて考えるだけで良い。

次に、なぜ結合して良いのかについて。
点Pを基点に点を追加して長方形を作成するためには、問題文の条件から、
・点Pと同じx座標を持つ点X1& 点Pと同じy座標を持つ点Y1
・点Pと同じx座標を持つ点X2, 点X2と同じy座標を持つ点Y2
・点Pと同じy座標を持つ点X3, 点X3と同じx座標を持つ点Y3
これらのパターンのどれかの点Xと点Yが同時に存在することが必要になる。
「点Pのx座標[Px]が含まれる集合があること」は、同じx座標を持つ点Xがあることを示す。
また、集合は同じy座標を持つ点について考えており、重複する要素がある場合は結合するが、「重複して集合の要素数が増加する=結合前の集合はそれぞれ少なくとも要素が2つ以上存在する」ことが言える。
集合を結合するとy軸の値の情報を無くしてしまうが、重複した要素は別の集合とのy軸の違いの架け橋になってくれる。
重複した点を点A(Ax, Ay)とすると、(点A, 追加された点(Ax, Py), 結合したい集合に含まれる点)を元に新たに長方形を作成できる。
よって、結合しても問題なく長方形を作成することができる。


話は戻って、結合した集合を作成できれば、後は数え上げるだけである。
点Qを基点にして考える場合、点Qのx座標が含まれる集合の要素数-1(自身の分は追加しない)だけカウントを追加する。
全ての点に対してこの操作を行うと、「同じy座標に対して何度も点の追加作業をしてしまう」という問題が発生する。
重複で追加をしなくても、先程は考えなかった、「追加すべき点に既に点があった場合、無駄に点を追加してしまう」という問題がある。
これらの問題を解決するために、以下の操作を行う。
・点を追加したy座標を記録する。
・点Qのy座標がすでに記録されていた場合、点の追加は行わず、自身と重複する点の追加を防ぐためにカウントを-1する。


実装
後で書くかも


頭の中のイメージはほとんど完成してるのに実装に結構時間を取られた。
集合の結合なんてせずに、○○が含まれる集合簡単に列挙できるデータ構造とかコンテナの使い方とか知ってればもっと楽だったんだけどあるのかしら。
どうやって実装するかの部分で悩んだのは結構久々だった。


今日はABC・・・と思ったら明日に延期されたみたいですね。
21:00開始予定だったけど実は18:30時点でもう結構眠いので延期されてよかった。