はじめに

競プロ勉強会第5回です。今回は集合を扱うデータ構造、座標圧縮、二分探索の話をします。とりあえず詰め込めるもの詰め込んでみた的な。今回の話はABCでとても良く出る典型of典型です。マスターしましょう。

目次
はじめに
1. set
2. Union Find
3. 平衡二分探索木
4. 座標圧縮
5. 列の二分探索
6. 解の二分探索

1. set

皆さんsetって使った事ありますか?ABC-C問題くらいで、使うとシンプルに解ける事が多い印象ですね。高難易度の問題でも部分的に使うことでシンプルになる問題もたまに見かけます。 setは集合を管理するデータ構造で、集合の中に要素を入れる、要素が入っているかなどができます。コードを見てみましょう。

set<int> st;
st.insert(5); // 5を入れる
if (st.count(4) == 1) {
  // 4が集合に入っている時
}
auto it = st.lower_bound(3); // 3以上で最も小さい要素のイテレータが返ってくる
if (it != st.end()) { // 要素が無い場合も考慮
  cout << *it << endl; // ポインタと同じ要領で扱える
}
it++; // イテレータを次に移動 つまりその次に大きい値のイテレータになる
st.erase(it); // 要素削除 ここらへん使う時ネットで調べて。
// 削除するとイテレータが壊れてしまうかもしれないので注意(そこらへんの挙動に詳しくない)

イテレータの使い方、教わる事が無かったかもしれないですが、便利なので知っておこう。set上のlower_bound()は割と使う。algorithmの中のlower_bound(st.begin(), st.end(), 3);を使うとO(n)になるので注意。操作はだいたいO(log n)でできる。

setには各要素1個しか入らない。重複を許したい時はmultisetを使おう。ちなみにmapは内部的にset<pair<key, value>>だった気がする

2. Union Find

今日の目玉。これは集合を扱う、というか元々要素があって同じグループにするのと同じグループかの判定を効率的に判定する。機能としては init(n) := 0からn-1のn個の異なるグループの要素を作る merge(a, b) := aとbを同じグループにする isSame(a, b) := aとbは同じグループかが要件。皆さんならどう実装しますか？

各要素が同じグループの要素を持つのは論外ですね。ちょっと賢い人ならグループの代表を適当に決めて、代表が同じかを判定に問題すり替えできるのかな?mergeする時、それぞれの代表を調べて、どっちか一方の代表を代表じゃなくすればいい訳です。

離散の知見のある人ならこれは木構造とみなせるって気づくかな。代表=木の根、merge=どっちか一方の根の親をもう一方の根にする。ここで木の根を求める関数をfind(x)とする。

それでも最悪O(n)かかる。ここで重要な工夫点は

サイズの大きい木に小さい木をくっつける。
一度find(x)をすると、途中の点を見る必要は無いので、途中の点の親を木の根に書き換える

どちらか一方実装すると平均O(log n)に落ちます。1はデータをマージする一般的なテクニックって名前が付いていて有名です。1がO(log n)になる証明は簡単で、mergeによって根の親が決まる時、サイズは必ず2倍以上になります。よって、木の高さはlog n以下になるという訳です。賢いですね。1, 2両方実装すると、計算量は平均アッカーマン関数の逆関数になるらしいです。理解できてないけど殆ど定数と考えてよいものらしい。

問題では集合のサイズを聞かれる事もあるため、サイズありのやつを書きました。parには根以外の時親番号が、根の時-(集合のサイズ)が入っています。-なのは、親か親じゃないかを負かどうかで判定するため。普段使いにはライブラリがあれば十分ですが、Union Findを応用したデータ構造を理解する時に必要になるので動作原理は理解しておきましょう。

typedef long long ll;
// 僕のライブラリは全部llに統一している
class UnionFind {
  vector<ll> par, rank; // par > 0: number, par < 0: -par
public:
  UnionFind(ll n) : par(n, 1), rank(n, 0) {}
  ll getSize(ll x) {
    return par[find(x)];
  }
  ll find(ll x) {
    if (par[x] > 0) return x;
    return -(par[x] = -find(-par[x]));
  }
  void merge(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      par[y] += par[x];
      par[x] = -y;
    } else {
      par[x] += par[y];
      par[y] = -x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }
  bool isSame(ll x, ll y) {
    return find(x) == find(y);
  }
};

使い方は

UnionFind uf(n); // n個の独立した要素を作る
uf.merge(a, b); // a, bをマージ
uf.isSame(a, b); // a, bが同じか
uf.getSize(a); // aのサイズを得る

Union Findを応用するデータ構造として

ポテンシャル付Union Find: aとbの差を定義できる
部分永続Union Find: 過去を遡ってisSameやgetSizeを調べる事ができる
Undo可能Union Find: undoができる。stackで持つだけ

など。部分永続は難しい問題で見かける。

純粋なUnion Findの応用例で、直感に反する難しい問題として関係を表現できる事が挙げられる。例えば、

n人の人がいて、グー、チョキ、パーの札をいずれか一つ持っています。2整数が書かれたm個のデータセットが与えられます。 a b := aとbが札を用いてじゃんけんするとaが勝つ。但し、過去のデータと矛盾するデータが与えられる事があります。矛盾するデータはどれかを答えなさい(矛盾するデータは以降に影響を与えないものとする)

独特な雰囲気の問題ですね。各人が何を持っていたかの情報は与えられないので、解をとりあえず決める事ができませんね。

ここでaがbに勝つということは、aがグーならbはチョキ、aがチョキなら...(略)と言い換える事ができます。これは関係を表していますね。

突拍子に思えるかもしれませんが、3n個の要素を作っておきます。つまり、n人に対してグー、チョキ、パーの3通りの状態を持ちます。

aがbに勝つという事は、aのグーとbのチョキを同じグループにします。他2つも同様。矛盾があるという事はaのグーとbのグー、あるいはbのパーが同じグループだった時起こります。そいつを報告してあげればよいです。

ではこれに追加でxの持っている札を与えるクエリも含んだらどうすればいいでしょう？

その時はゴミ箱的な頂点(nullと呼びましょう)を1つ作っておき、それに繋がっている要素はありえないものとして扱えばよいです。

xがグーである→xのグーがnullと繋がっていれば矛盾、そうでなければxのチョキ、パーとnullを結ぶ aがbに勝つ→aの手が決まっているか/bの手が決まっているかの4通りを場合分けすればいいです。きれいな解法あるのかな？

3. 平衡二分探索木

いりません。あると非想定解で殴れるのでうれしいですが。というかsetも平衡二分探索木です。

4. 座標圧縮

座標の位置が重要では無く、他の座標との位置関係が重要な時に用います。例えば、x, y平面があり、 $10^3$ 個くらいの長方形(辺はx or yに平行)が与えられる。その長方形内を黒色で塗る。連結なものをひとかたまりとして考えると、何グループあるか？みたいな問題。全探索は無理だけど、長方形の端点のx, yは高々O(n)個で、その位置自体には興味が無いのでx方向、y方向それぞれ座標圧縮して小さい方から0, 1, 2, ...と座標を振り直す。すると全探索してもO( $n^2$ )なのでセーフみたいな。

template <typename T>
class Zip {
  vector<T> d;
  bool flag;
  void init() {
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    flag = false;
  }
public:
  Zip() {
    flag = false;
  }
  void add(T x) {
    d.push_back(x);
    flag = true;
  }
  ll getNum(T x) {
    if (flag) init();
    return lower_bound(d.begin(), d.end(), x) - d.begin();
  }
  ll size() {
    if (flag) init();
    return (ll)d.size();
  }
};

使い方は

Zip<int> zx, zy;
for (ll i = 0; i < n; i++) {
  zx.add(x[i]);
	zy.add(y[i]);
}
for (ll i = 0; i < n; i++) {
  x[i] = zx.getNum(x[i]); // x[i]に入れ直し
	y[i] = zy.getNum(y[i]);
}
// その後全探索

難しい事はやって無いけど知らないと思いつかないかな。

5. 列の二分探索

ソート済みの配列dに対してx以上の最初の要素を求めよう

x以上の最初の要素は最初(-1, n]の範囲にある。(解がnの時存在しない)解が(a, b]にあるとしよう。もし中間地点midがx以上なら、解は(a, mid]内にあるし、そうじゃないなら解は(mid, b]内にある。1回の操作ごとにサイズが半分になるので、O(log n)で求める事ができる。

二分探索の概要は簡単だと思うけど、実装する時どちらが閉区間でどちらが開区間かを考えるのと初期地点(±1)を決めるのが面倒。例えばx以下の最初の要素なら[-1, n)の範囲。

覚え方は 閉じてる方を最終の解にする。開いている方はありえない値にする。 めぐる式にぶたんの方が分かりやすいかも？僕はこっちの説明の方が好きなので書きません。分からなかったら調べてみて。

配列、vectorならalgorithmの中のlower_boundを使えます。

#include<algirothm>

int d[100];
int i = lower_bound(d,  d+100, x) - d; // lower_bound自体はポインタが返ってくる。こう書くとその要素番号が得られる

vector<int> d2;
int j = lower_bound(d.begin, d.end(), x) - d.begin(); // 同じく。イテレータが返ってくる。イテレータのまま扱ってもヨシ

upper_boundでxより大きい最初の要素が得られます。x以下を求める関数は無い。(これは当たり前で、d.end()がn番目に相当し番兵の役割を果たすが、前方向に番兵は存在しないため)欲しい時はxより大きいものを求めて-1すればいいです。

ちなみに

int count = upper_bound(d, d+100, x) - lower_bound(d, d+100, x);

でちょうどxのものの数が得られる。知見。

6. 解の二分探索

解を直接求める事は困難だけど、解を決めてその解が条件を満たすかを判定する関数が簡単に作る事ができ、解の区間が連続であるなら二分探索が使えます。ABC-Dくらいでよくみる。難しい問題に出会った時は 判定関数なら簡単に出せるかな？、出せるなら解は連続？ と問うといいでしょう。慣れればある程度の問題なら雰囲気で一瞬で分かる。

大事な事は 判定関数を分離する事！！！ 分離できると、やる事は上と同じで、

bool check(int x) { // 判定関数
  return true or false;
}

int solve() {
	int lb = -1, ub = n; // 解が(lb, ub]の時
	while (lb + 1 < ub) {
		int mid = (lb + ub) / 2;
		if (check(mid)) ub = mid;
		else lb = mid;
	}
	return ub;
	// めぐる式の方がきれいに抽象化できる?
}

もし解が実数なら

constexp double EPS = 1e-7;
// ...
while (lb + EPS < ub) // ...

とすればいいです。例を考えてみましょう。

n本の棒があり、長さは $a_i$ 。それを切ってm本の同じ長さの棒を作りたい。最大作れる長さは？

解けますね？