C++ STLのmultiset（Set）を使って反転数をカウントする方法

このチュートリアルでは、C++ STLの set（正確には multiset）を使用して、配列の反転数（転倒数）をカウントするプログラムについて解説します。

反転数（転倒数）とは？

反転数とは、配列が完全にソートされた状態からどれだけ離れているかを測る指標です。具体的には、インデックスが i < j であるにもかかわらず arr[i] > arr[j] となっている要素のペアの総数を意味します。

配列がすでに昇順にソートされている場合、反転数は 0 になります。逆に、配列が逆順に並んでいる場合は反転数が最大値となり、その値は n*(n-1)/2 です。

アルゴリズムの考え方

multiset を使うと、以下の手順で反転数を効率よく数えられます。

1. 配列の先頭要素を multiset に挿入します。
2. 2番目以降の各要素について、まず multiset に挿入します。
3. 挿入した要素に対して upper_bound() を呼び出し、その要素より大きい値の中で最初の位置を取得します。
4. その位置から末尾までの要素数を distance() で数え、反転数に加算します。

こうすることで、「現在処理中の要素より前に現れた、値が大きい要素」の個数、つまり反転のペア数を累積的に求めることができます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;

// 反転数を返す関数
int get_Icount(int arr[], int n){
    multiset<int> set1;
    set1.insert(arr[0]);
    int invcount = 0; // 結果の初期化
    multiset<int>::iterator itset1;
    for (int i = 1; i < n; i++){
        set1.insert(arr[i]);
        itset1 = set1.upper_bound(arr[i]);
        invcount += distance(itset1, set1.end());
    }
    return invcount;
}

int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr) / sizeof(int);
    cout << "Number of inversions count are : " << get_Icount(arr, n);
    return 0;
}

実行結果

Number of inversions count are : 6

配列 {8, 4, 2, 1} の場合、反転しているペアは (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) の6組であるため、出力は「6」となります。

計算量について

multiset への挿入と upper_bound() はそれぞれ O(log n) で動作しますが、distance() は双方向イテレータに対して線形時間 O(n) かかるため、全体の時間計算量は O(n²) となります。より大きな配列を扱う場合は、Binary Indexed Tree（BIT）やマージソートを利用する手法により、O(n log n) まで高速化できます。