文書の過去の版を表示しています。
転倒数
具体的な例でイメージすると、{3,10,1,8,5} のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。
これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。
例の場合、(3,1)(10,1)(10,8)(10,5)(8,5) の5つの組で、左にある数字が右より大きくなっているので、転倒数は5である。
実際にやってみると、
3 10 1 8 5 3 1 10 8 5 3 1 8 10 5 3 1 8 5 10 1 3 8 5 10 1 3 5 8 10
たしかに5回で並び替えられる。
転倒数の求め方
数列の各要素について、独立に考えることが出来る。
つまり、「自分より右にある、自分より小さな数の個数」を、全要素求めて足し合わせると、それが転倒数となる。
3→ 10 1 8 5 : 1 の 1つ 10→ 1 8 5 : 1,8,5 の 3つ 1→ 8 5 : なし 8→ 5 : 5 の 1つ 5→ : なし 1+3+1 = 5
また、「自分より左にある、自分より大きな数の個数」でも同じ事である。
3 10 1 8 ←5 : 10,8 の 2つ 3 10 1 ←8 : 10 の 1つ 3 10 ←1 : 3,10 の 2つ 3 ←10 : なし ←3 : なし
「自分より左にある、自分より大きな数の個数」を高速に求めるには、 Binary Indexed Tree を用いる方法が使われる。
BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造である。
- 数列{a1,a2,...,an}があり、最初、全ての要素は0である
- 以下の2つの要求を処理する
ADD(i, x)
: aiにxを加算(1≤i≤n)SUM(t)
: a1からatまでの合計を得る(1≤t≤n)
これを用いて、以下のように算出する。
BITを用意
まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。
数列を先頭から順番に処理する
i 番目(1-indexed)の項を pi とする。各項に付き、以下の2つの処理を行う。
BITに加算する
ADD(pi,1)(BITの pi の位置に、1を加算する)
自分より左にある自分より大きい数の個数を求める
先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。
自分より左で pi より小さい数の個数は、SUM(pi)(BITで 1~pi の和)を求めることで得られる。
逆に言うと、pi より大きい数の個数は、i−SUM(pi) である。
数列の各要素につきこれを足し合わせることで、転倒数が得られる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Bit: def __init__( self , n): self .size = n self .tree = [ 0 ] * (n + 1 ) def sum ( self , i): s = 0 while i > 0 : s + = self .tree[i] i - = i & - i return s def add( self , i, x): while i < = self .size: self .tree[i] + = x i + = i & - i ppp = [ 3 , 10 , 1 , 8 , 5 ] bit = Bit( 16 ) ans = 0 for i, p in enumerate (ppp): bit.add(p, 1 ) ans + = i + 1 - sum (p) print (ans) |