転倒数 アルゴリズム
転倒数 (inversion number) とは?
数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき,
i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という.
たとえば a = {3, 1, 5, 4, 2} のとき,
i < j かつ a_i > a_j となっている組は,
(3, 1), (3, 2), (5, 4), (5, 2), (4, 2) の 5組であるから転倒数は 5 となる. (添字ではなく要素の組を列挙した)
転倒数は下記のようなバブルソートを行った際の交換回数と等しくなることが知られている. 一回の交換で反転数は1減少し, ソートが完了すると反転数は0となるのでそれはそう.
#!/usr/bin/env python3 def bubble_sort(A): cnt = 0 for i in range(len(A)): for j in range(len(A)-1, i, -1): if A[j] < A[j-1]: A[j], A[j-1] = A[j-1], A[j] cnt += 1 return cnt
直感的には転倒数は昇順ソートされた状態を正しい並びとしたとき, 正しくない並びとなっている組の数と考えることができる.
転倒数を愚直な実装で求めると時間計算量は となるが以下に示すように
のアルゴリズムが存在する.
Fenwick Tree(Binary Indexed Tree)を用いる方法
i < j かつ a_i > a_j を満たす要素を数えるには以下の 2 つの方法が考えられる.
i についてループを回し i < j かつ a_i > a_j となるものを数える.
j についてループを回し i < j かつ a_i > a_j となるものを数える.
どちらもほぼ同じように見えるが, 後者のように考えないとうまくいかない.
後者の方法で i < j かつ a_i > a_j となるものを数えるとき Fenwick Tree を使うと各 j について で求めることができる.
Fenwick Tree は区間の和の計算, 要素の値の更新がそれぞれ でできるデータ構造.
- C++ による Fenwick Tree の実装例
struct fenwick_tree { typedef int T; T n; vector<T> bit; // 各要素の初期値は 0 fenwick_tree(T num) : bit(num+1, 0) { n = num; } // a_i += w void add(T i, T w) { for (T x = i; x <= n; x += x & -x) { bit[x] += w; } } // [1, i] の和を計算. T sum(T i) { T ret = 0; for (T x = i; x > 0; x -= x & -x) { ret += bit[x]; } return ret; } // [left+1, right] の和を計算. T sum(T left, T right) { return sum(right) - sum(left); } };
使い方
Fenwick Tree は最初 a = {a_0, a_1, a_2 ... a_n-1} の数列があり, 各要素の初期値は 0 となっている.
j = 0 から n-1 までループを回し. 以下のような処理をすることで転倒数を求めることができる.
fenwinck_tree f_tree(n); for (int j = 0; j < n; j++) { ans += j - f_tree.sum(a[j]); f_tree.add(a[j], 1); }
fenwick tree の i 番目の値が x であるとき, 値が i である要素が x 個あるものとみなす. すると sum(a[j]) が返す値は i < j かつ a_i <= a_j の個数となる. なぜなら sum(a[j]); が実行されるとき fenwick tree に追加されている数列の要素は必ず, 現在の j より小さいときに追加されたものであり(i < j を満たす), sum(a[j]) は区間[1, a[j]] の和であるから.
数えたいのは i < j かつ a_i > a_j であるから, 現在見ている数列の要素の個数である j から sum(a[j]) を減算した値を足せば良い.
注意点としては size n の tree を作成する際の n の値は数列の最大値より大きなものを設定する必要があるという点と, 数列の要素に0以下のものがあると要素の追加ができないので下駄を履かせる必要があるという点である.
分割統治法を使う方法
以下のようなコードでマージソートを行いながら転倒数を求めることもできる. (引数として渡した配列はソートされてしまう破壊的な関数である点に注意!!!)
long long merge_cnt(vector<long long> &a) { int n = a.size(); if (n <= 1) { return 0; } long long cnt = 0; vector<long long> b(a.begin(), a.begin() + n / 2); vector<long long> c(a.begin() + n / 2, a.end()); cnt += merge_cnt(b); cnt += merge_cnt(c); int ai = 0, bi = 0, ci = 0; // merge の処理 while (ai < n) { if (bi < (int)b.size() && (ci == (int)c.size() || b[bi] <= c[ci])) { a[ai++] = b[bi++]; } else { cnt += n / 2 - bi; a[ai++] = c[ci++]; } } return cnt; }
与えられた数列を A とし, その数列を B と C に分割(Devide)する.
B, C をそれぞれソート済みとすると, Aの転倒数はBの転倒数とCの転倒数を足し, さらにBとCとの間にまたがって存在する i < j かつ a[i] > a[j] となるような組の数を足したものとなる.
数列 a = {3, 1, 5, 4, 2,} を例として考える. merge_cnt() が実行されると, 数列は以下のように再帰的に分割される.
A = {4, 2}, B = {4}, C = {2} とする. B と C はそれぞれサイズが1なので転倒数は0である.
BとCを merge するとき, cnt がどのように更新されるかを見る.
while (ai < n) { if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) { a[ai++] = b[bi++]; } else { cnt += n / 2 - bi; a[ai++] = c[ci++]; } }
数列 C の要素が Aに merge されるとき (i < j), cnt は更新されている. これは転倒数の定義 (i < j and a[j] < a[i] となる i, j の組の数) を考えれば当然である.
cnt += n/2 - bi; の n/2 は数列B のサイズを表している. bi は BのインデックスでBの要素全てがAに代入されると n/2 となる.
数列Cの要素が merge されるとき, 数列 B のうちまだ merge されていない要素の個数を cnt に足している.
merge の処理が済んだ数列はきちんとソートされる.
分割された数列の転倒数を赤で示したのが下図である.
使用例
AOJ: ALDS1-5 D
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp
Fenwick Tree による解答例
- http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3395873
- 109 個の配列を確保はできないので map を使って数列を置換する.
- 分割統治による解答例