文書の過去の版を表示しています。
std::setを使わない代替テクニック
競技プログラミングでは、C++ に std::set という(事実上)平衡二分探索木ライブラリがあるから、たまにその使用を前提とした問題が出る。
std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる(set - cpprefjp C++日本語リファレンス より一部抜粋)
機能 | 概略 | 計算量 |
---|---|---|
insert | 集合に要素を追加 | $O(\log{N})$ |
erase | 集合から要素を削除 | $O(\log{N})$ |
upper_bound lower_bound | ある値より大きい最小の要素の探索 | $O(\log{N})$ |
Pythonでは標準ライブラリにないし、実装してもリストアクセスの遅さからTLEに直面することがままある。
いや、実際には、別に使わなくても何とか別の方法がある場合が多いが、std::setが「使えば一発」なのに対し、問題依存の考察や実装の手間を要するのが常である。
(素直にC++
で書けって?そりゃそうだ)
std::setを使いたいけど使えない……という場合に、代わりになりうる方法をメモ。
代替方法一覧
問題に出くわすごとに列挙していき、ある程度蓄積されたら分類方法を考える。
- Binary Indexed Tree
- 最も汎用性のある代替方法
- 優先度付きキュー (heapq)
- 一定の制約の上で簡単&高速
- 問題依存の上手い方法
- 列挙していけば何か共通点みたいなのが見つかるかも知れない
- C++コードを埋め込んで外部モジュールとしてコンパイル
- Pythonでも高速に動く平衡二分木を使う
- 参考
Binary Indexed Tree
最も汎用性の高い置き換え。std::setは言うて単純な機能しか持ってないが、こちらなら追加の機能実装も可能。
- 集合に、値を追加したり削除したりする
- 任意のタイミングで、小さい方から $k$ 番目の値を答えよ。$k$ は可変である。
- 制約
- 値の取り得る範囲は $1~10^6$(配列を作れる)程度
Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 詳細はBinary Indexed Tree(Fenwick Tree)参照。
- 値 $x$ を追加 → $bit.add(x, 1)$
- 値 $x$ を削除 → $bit.add(x, -1)$
- $k$ 番目の値を取得 → $bit.lower\_bound(k)$(累積和が $k$ 以上になる最小のindexを取得)
- $x$ 以下の最大の値を取得 $bit.lower\_bound(bit.sum(x))$
- $x$ 以上の最小の値を取得 $bit.lower\_bound(bit.sum(x - 1) + 1)$
機能 | 計算量 |
---|---|
insert | $O(\log{N})$ |
erase | $O(\log{N})$ |
upper_bound lower_bound | $O(\log{N})$ |
$x$ 以下の最大の値が存在しない場合、$1$ が返る。
$x$ 以上の最小の値が存在しない場合、$N+1$ が返る。
(※BITを1-indexedで実装していた場合。lower_boundの実装内容にも依るが)
そのような操作が発生しうる場合、indexをずらして、$i=1$ は空白要素として $i=2$ から本来の値を入れる、などで本当の値と区別できる。
例
累積和 std::set 初期状態 1 2 3 4 5 6 7 8 [0 0 0 0 0 0 0 0] {} 5を追加 [0 0 0 0 1 1 1 1] {5} 3を追加 [0 0 1 1 2 2 2 2] {3, 5} 小さい方から2番目を取得 [0 0 1 1 2 2 2 2] {3, 5} ^ 累積和で"2"が始まるiは「5」 2,3,7を追加 [0 1 3 3 4 4 5 5] {2, 3, 3, 5, 7} 4以下の最大の値を取得 [0 1 3 3 4 4 5 5] {2, 3, 3, 5, 7} ~ 累積和で 4 の箇所は"3" ^ 累積和で "3" が始まるiは「3」 6以上の最小の値を取得 [0 1 3 3 4 4 5 5] {2, 3, 3, 5, 7} ~ 累積和で 6-1=5 の箇所は"4" ^ 累積和で 4+1=5 が始まるiは「7」 7を削除 [0 1 3 3 4 4 4 4] {2, 3, 3, 5} 6以上の最小の値を取得 [0 1 3 3 4 4 4 4] {2, 3, 3, 5} ^ 存在しない場合、N+1 が返る点には注意
バリエーション
値の範囲がこれを越える場合
値の取り得る種類数が $N=10^6$ 程度で、かつ先読みできる場合、前もって圧縮して $1~N$ に対応づければよい。
前後の値を取得
BIT上の二分探索では、累積和が $k$ 以上になる要素そのものは分かっても、前後の値はたどれない。
この方法では前後の値を求めたい場合は $k \pm 1$ で累積和の二分探索を改めて行うしかない(と思う)。
ただし、小さい方の値を求める際、以下の方法で少しだけ省略できる場合がある。
累積和の探索では、その過程で、累積和が $k$ 以上になる最小の要素を $x$ として「$x$ 未満の要素の個数」も求めることになる。 (これを $L[k]$ と表す)
- $L[k]=k-1$ なら、改めて累積和が $k-1$ 以上になる最小の要素を二分探索
- $L[k] \lt k-1$ なら、$x$
優先度付きキュー
- 値が追加されたり削除されたりする
- 任意のタイミングで、小さい方から $k$ 番目の値を答えよ
- 制約
- $k$ は固定である
上記のような制約があれば、2つの優先度付きキューを用いることで代替できる。
Binary Indexed Treeでは実現できない、$10^9$ など配列を作るのが厳しい範囲のクエリにも対応できる。
- lower: 常に値の個数を $k$ 個に保つ優先度付きキュー。大きい方から取り出す
- upper: $k$ 個から溢れた分を管理する優先度付きキュー。小さい方から取り出す
答えは常にlowerの先頭に位置する($x$ とする)。新しい値 $y$ が来たとき、
- $x \le y$ なら、$y$ をupperにpush
- $x \gt y$ なら、$x$ をlowerよりpopし、代わりに $y$ をpush。$x$ はupperにpush
機能 | 計算量 |
---|---|
insert | $O(\log{N})$ |
erase | $O(\log{N})$? 下記バリエーション参照 |
get_k_th | $O(1)$ |
バリエーション
$k$ 番目でなく中央値を求めよ
lowerとupperの要素数が同じになるように保ちながら追加していく。
$k$ 番目の値を削除せよ
削除されるのが $k$ 番目の値に限定されるなら、つねに優先度キューの先頭にあるので可能。
任意の値を削除せよ
優先度キューとは別に、「値が生き残っているか」を管理するデータを用意する。
- 要素に重複が無い場合
- 「値:$x$ は生き残っているか」を管理するデータ
- 要素に重複がある場合
- 要素にIDをつける
- 「ID:$i$ は生き残っているか」を管理するデータ
- lowerで生き残っている要素数を管理する変数 $lc$(lowerの個数が $k$ 未満になる可能性のある場合)
- lower, upperで生き残っている要素数を管理する変数 $lc, uc$(中央値を求める場合)
値 $y$ を削除するとき、lowerの先頭 $x$ と比較して、
- $x \lt y$ なら、$y$ を削除済みにする
- $x \ge y$ なら、$y$ を削除済みにし、upperからlowerに1要素移す
popするとき、それが生き残っている値かどうかを確認し、削除済みなら無かったこととして続けてpopする。
配列・特殊アイデア系①
一概には言えないけど、だいたい以下のような問題に適用できうる。
- 順列など、全ての要素が異なる配列を考える
- 各要素について、「自分の左(右)で自分に最も近い、自分より小さな(大きな)値の位置」を求めたい
Binary Indexed Tree でもいいんだけど、より高速で、なかなかアイデアが綺麗な解法。
std::set解(想定解)
std::setであれば、値の小さい順に「要素のindex」をinsertしていく方法が考えられる。
ある要素 $A_i$ を挿入しようとしたとき、既にset内にあるのは自身より小さな要素のindexに限られる。 そこから $i$ 未満で最も大きい数を検索すれば、それが $A_i$ にとって、自身より小さな左で直近の要素の位置である。
代替手法
各要素の暫定解を表す配列を用意して、値の大きい順に処理して更新していく。
- $L$: 自身より左で、自身より小さい直近の要素のindex(暫定)
- $R$: 自身より右で、自身より小さい直近の要素のindex(暫定)
ある要素の処理が終わったら、後から処理される要素のために、自身をスキップさせるよう更新する。
横一列に繋がったグラフの辺を繋ぎなおすと考えるとわかりやすい。
【初期状態】 i 1 2 3 4 5 6 ③--①--④--⑥--⑤--② L 0 1 2 3 4 5 自身より左で自身より小さい要素の i (暫定) R 2 3 4 5 6 7 自身より右で自身より小さい要素の i (暫定) はじめはすぐ左・すぐ右の位置を入れておく 【最も大きい要素⑥】 処理された時点のL,Rの値がそのまま答えとなる。 最初はどの要素も自分より小さいので、すぐ左・すぐ右のindexとなるのは当然。 i 1 2 3 4 5 6 ③--①--④--⑥--⑤--② L 0 1 2 [3] 4 5 R 2 3 4 [5] 6 7 次の処理のために、⑥を抜いて、④と⑤を直結させたい。 i 1 2 3 4 5 6 ③--①--④------⑤--② L 0 1 2 _ 5 R 2 3 _ 6 7 そのためには、以下のように更新すればよい L[R[i]] = L[i] R[L[i]] = R[i] 今回に当てはめると、 L[5] = 3 L[3] = 5 i 1 2 3 4 5 6 ③--①--④------⑤--② L 0 1 2 [3] 5 R 2 3 [5] 6 7 【2番目に大きい要素⑤】 同様に、この時点での L[i]=3, R[i]=6 が⑤にとっての答え i 1 2 3 4 5 6 ③--①--④------⑤--② L 0 1 2 [3] 5 R 2 3 5 [6] 7 同様に更新すると、ちゃんと④と②がつながる i 1 2 3 4 5 6 ③--①--④----------② L 0 1 2 [3] R 2 3 [6] 7
これを繰り返すと、$O(N)$ で求められる。std::setを使うと $O(N\log{N})$ なので、それより高速である。
バリエーション
順列で無い場合(同じ要素は含まれない)
値が飛び飛びなら、先読みできるなら圧縮すればよい。先読みできない場合は……わからん。
同じ要素が含まれる場合
同じ値が含まれると、同率の処理が上手くいかない。
一応、自身の値 “以下” の直近の位置を求めればいいなら、方法がある。
- $L[i],R[i]$ の取得を同率の要素ごとにまとめて行い、更新は全ての同率の要素が終わった後で一括に行う
自身の値 “未満” なら……どうやればいいだろうね。
ピボット木
上記で紹介されている平衡二分探索木。結構速いみたい。
- 制約
- 載せられるのは整数値のみ
- $1~2^K-1$ までの整数値を入れられて、$K$ は最初に決定する必要がある(後から拡張はやろうと思えばできる)
- 同じ値は複数持てない
- できること($N=2^K$ として)
- 挿入 $O(\log{N})$
- 削除 $O(\log{N})$
- ある値が存在するかの検索 $O(\log{N})$
- ある値より大きい・小さい直近の値の検索 $O(\log{N})$
メリットとして、入れる値が整数なら上限値が $10^9$ などのように大きくても座標圧縮が必要ない。
(BIT木のように最初に配列を作るのでは無く、挿入ごとにノードインスタンスを作るので)
アイデアとしては、各ノードは、自身の位置に応じたpivot値を持つ。
たとえば値 $x$ を挿入するとき「上から挿入箇所を辿っていって、pivot値が $x$ と等しいノードに来たら $x$ はそこでFIXし、代わりにそこに入っていた元の値の挿入箇所をその地点から探し始める」ようなことを行う。
これにより、高さが最初に決めた $K$ 以上にならないことが保証されるとともに、他の平衡二分探索木で発生する「回転操作」、つまりは左右の子を繋ぎ替えるなど、値の書き換えを減らしている。
バリエーション
実数値を載せる
ピボット値を小数範囲に拡張して、$0.5, 0.25, 0.125, ...$ 単位まで探索できるようにする。
ただし、探索深さの上限が保証されなくなる。(まぁ、極端に狭い範囲に多くの値が集中しない限り実用的に問題となることは少ないはず)
複数の整数のTupleを載せる
bitshiftして1整数にまとめてやる。
値の上限が大きくなると計算量も増えるが、例えば上限 $10^6$ の整数を3つ管理しても約 $2^60$、$K=60$ なので、そこまで無理なものではない。
同じ値を持つ
辞書などで各値の個数を管理して、削除時に個数が“0”にならない限りは削除しない、みたいな拡張でいけそう。
$k$ 番目を求める
ノードに自身の部分木以下のノードの個数を持たせておく。