競プロ参戦記 第10回「転倒数」 Chokudai Speed Run 001 [J]
典型問題を解きました。自作ライブラリの検証もかねて。
Chokudai Speed Run 001
J - 転倒数
問題概要：バブルソートの交換回数を求めよ
考察
バブルソートは有名なソートアルゴリズムです。Rust で書くとこう：
fn bubble_sort(xs: &mut [i64]) -> i64 {
let n = xs.len();
let mut k = 0;
for l in 0..n {
for r in (l + 1..n).rev() {
if xs[r - 1] > xs[r] {
xs.swap(r - 1, r);
k += 1;
}
}
}
k // 交換回数
}明らかに O(n^2) 時間かかります。高速に交換回数 k を求めたい。
具体的に交換を列挙してみましょう。a > b と書いている部分で交換です。サンプル1の場合：
3 1 5 4 > 2
3 1 5 > 2 4
3 > 1 2 5 4
1 3 2 5 > 4
1 3 > 2 4 5
1 2 3 4 5で、たしかに5回交換されます。
交換回数の性質を調べるため、要素のペアに注目します。例えば 3, 1 のように左側のほうが大きいペアは、ソートの途中で交換されます。最終的に配列は昇順になるので、このようなペアは必ず交換されます。一方、左側のほうが値が小さいペアは絶対に交換されません。
したがって交換回数は、もとの配列において左側のほうが値が大きいようなペアの数です。これを転倒数というようです。
これを計算するには、配列の各要素 a につき、それより左側にあって値が a より大きい要素の個数を計算すればいいです。例えば 3, 1, 5, 4, 2 なら
1 より左側にある大きい数は 1個 (3)
5 より左側にある大きい数は 0個
4 より左側にある大きい数は 1個 (5)
2 より左側にある大きい数は 3個 (3, 4, 5)
となり、正しく5個の「転倒したペア」がみつかります。
これは、 A[x] = (値 x の要素の個数) という配列をもっておけば A[a + 1] + ... + A[MAX] という区間和で求められます。
例えば 3, 1, 5, 4, 2 では、要素 4 をみている時点で A[1]=1, A[3]=1, A[5]=1 となっていて、 4 より大きい要素の個数は A[5] + A[6] + .. = 1 です。
区間和を高速に計算する方法はたくさんあります。しかし今回の問題では、区間和の計算ともとになる配列の更新が交互に起こるので厄介です。もとになる配列が変更されたとき、区間和を計算するためのデータ構造も一緒に更新しなければいけないからです。
例えば累積和の場合、配列の要素が変更されたら、その要素より後ろの総和をすべて再計算する必要があります。これは O(N) 時間もかかるので、今回の用途では遅いです。
今回は BIT を使いました。(後述)
(追記 2018/11/25)
BIT について
BIT のソースコード全体は上記の回答か 自作ライブラリ を参照。
BIT についてはあらかた以下の PDF で説明されています。図が豊富でとても分かりやすいです。
以下に基本的な部分の説明を改めて書きます。実は先日まで自作ライブラリの BIT 実装にバグがあって、不安になってこの問題を解いた…という経緯があり、正確性についてはややあやしいです。でも説明したら理解が進むはず。
**BIT** (binary indexed tree) は区間和を高速に計算できるデータ構造です。区間和が対数時間で求められる上に、先述の通り、もとになる配列が変更されても対数時間で更新できます。
BIT は名前の通り木構造です。イメージ図：
[ 8 ] ..
[ 4 ] [ ..
[ 2 ] [ 6 ] [ ..
[ 1 ] [ 3 ] [ 5 ] [ 7 ] [ ..
..
< 0 > < 1 > < 2 > < 3 > < 4 > < 5 > < 6 > < 7 > < ..ここで [i] は BIT のノード i を表し、 <j> は区間和のもとになる配列の要素 j を表しています。[i] はその真下にある区間を「カバー」します。例えばノード [2] は要素 <0> <1> をカバーします。
区間 [0, r) (0以上r未満) の総和を求めるにはどうすればいいでしょうか。r を2進数展開すると面白い法則がみえてきます。例として r = 7:111 (2進数) とします。
区間 [0, 7) は [ 7:111 ] と [ 6:110 ] と [ 4:100 ] でカバーされます。
つまり **2進数での r の最下位ビットを1つずつ引いていくと、区間 [0, r) をカバーするノードを列挙できる** わけです。
ちなみに数 n の **最下位ビットは n & -n という式で求められる** そうです。Rust で書くとキャストがうるさいですが、こんな感じ:
fn rightmost_bit(n: usize) -> usize {
let s = n as isize; // 符号付きにする
(s & -s) as usize // 計算してから符号なしに戻す
}区間和の計算はこんな感じで、先述の通りノードを列挙しつつ、ノードが持っている値 (カバーする範囲の総和) を足していきます。
// [0, right) の区間和
pub fn bit_acc(bit: &Vec<i64>, right: usize) -> i64 {
let mut acc = 0;
let mut j = min(right, bit_len(bit)); // 区間を配列の長さでトリミング
while j > 0 {
acc += bit[j]; // ノード j がカバーする範囲の総和を足す
j -= rightmost_bit(j); // 最下位ビットを消す
}
acc
}次に BIT の更新です。繰り返しになりますが、もとになる配列のある要素の値が変化したら、その要素をカバーしているノードの値を再計算する必要があります。ここで操作するノードの個数は対数オーダー (O(log n)) なので、十分に高速です。
イメージ図の再掲：
[ 8 ] ..
[ 4 ] [ ..
[ 2 ] [ 6 ] [ ..
[ 1 ] [ 3 ] [ 5 ] [ 7 ] [ ..
..
< 0 > < 1 > < 2 > < 3 > < 4 > < 5 > < 6 > < 7 > < ..
ここでも面白い法則があります。要素 <j> をカバーするノードは、それに最下位ビットを足していくことで列挙できるようなのです。
例えば j = 5:101 なら、 5:101+1 = 6:110 と、 6:110 + 2:10 = 8:1000 で、結局 [ 5 ] [ 6 ] [ 8 ] の3つのノードです。
コードの例：
// 配列の index 番目の要素の値を value 増やす
pub fn bit_add(bit: &mut Vec<i64>, index: usize, value: i64) {
let mut j = index + 1; // ノードの番号を 1 始まりに直す
while j <= bit_len(bit) { // 配列の長さを超えない限り
bit[j] += value; // 総和に増えた分を足す
j += rightmost_bit(j); // 最下位ビットを足す
}
}まとめ：
1. 区間和を求めるには最下位ビットを引いていく
2. 区間和を更新するには最下位ビットを足していく