C++で「重要な逆ペア（Reverse Pairs）」を数える：マージソートによる効率的な解法

問題の概要

配列が与えられたとき、その中のペア（A[i] と A[j]）が次の条件を満たす場合、これを「重要な逆ペア（important reverse pair）」と呼びます。

• i < j かつ A[i] > 2 × A[j]

本記事では、このような重要な逆ペアの個数を求めます。たとえば入力が [2, 8, 7, 7, 2] の場合、条件を満たすのは (8, 2)、(7, 2)、(7, 2) の 3 組であるため、結果は 3 となります。

解法のアプローチ：マージソートの応用

すべてのペアを単純に調べる方法では計算量が O(n²) となり、配列が大きい場合に非効率です。そこで、マージソートのマージ処理を利用します。「ソート済みの左半分」と「ソート済みの右半分」を比較しながら統合する過程で条件を満たすペアを数え上げることで、計算量を O(n log n) まで抑えることができます。

アルゴリズムの手順

1. 答えを保持する変数 ans を 0 で初期化します。
2. merge() 関数を定義します（引数：配列 a、low、mid、high）。
3. k := high - low + 1 とし、サイズ k の一時配列 temp を作成します。
4. i := low、j := mid + 1、k := 0、first := mid + 1 で初期化します。
5. i <= mid の間、以下を繰り返します。
   • first <= high かつ a[first] × 2 < a[i] の間、first を 1 ずつ増やします。
   • j <= high かつ a[j] <= a[i] の間、temp[k] := a[j] とし、j と k を 1 ずつ増やします。
   • ans := ans + (first - (mid + 1)) を加算します（これは右半分の中で条件を満たす要素の個数に相当します）。
   • temp[k] := a[i] とし、i と k を 1 ずつ増やします。
6. j <= high の間、右半分の残りの要素を temp にコピーします。
7. k := 0 に戻し、i を low から high まで動かしながら a[i] := temp[k] として元の配列へ書き戻します。
8. calc() 関数を定義します（引数：配列 a、low、high）。low >= high の場合はそのまま return します。それ以外の場合は mid := low + (high - low) / 2 を計算し、calc(a, low, mid) と calc(a, mid + 1, high) を再帰的に呼び出した後、merge(a, low, mid, high) を呼びます。
9. solve() 関数を定義します（引数：配列 A）。ans := 0、n := A のサイズとし、calc(A, 0, n - 1) を呼び出して ans を返します。
10. メイン処理では solve(nums) の戻り値を返します。

C++による実装例

以下のコードで、実際の動きを確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int ans = 0;
    void merge(vector <int> &a, lli low, lli mid, lli high){
        lli k = high - low + 1;
        vector <lli> temp(k);
        lli i = low, j = mid + 1;
        k = 0;
        lli first = mid + 1;
        while(i <= mid){
            while(first <= high && (lli)a[first] * 2 < (lli)a[i]) {
                first++;
            }
            while(j <= high && a[j] <= a[i])
            {
                temp[k] = a[j];
                j++;
                k++;
            }
            ans += first - (mid + 1);
            temp[k] = a[i];
            i++;
            k++;
        }
        while(j <= high){
            temp[k] = a[j];
            k++;
            j++;
        }
        k = 0;
        for(lli i = low; i <= high; i++){
            a[i] = temp[k];
            k++;
        }
    }
    void calc(vector <int> &a, lli low, lli high){
        if(low >= high)return;
        lli mid = low + (high - low)/2;
        calc(a, low, mid);
        calc(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    lli solve(vector<int> &A) {
        ans = 0;
        lli n = A.size();
        calc(A, 0, n - 1);
        return ans;
    }
    int reversePairs(vector<int>& nums) {
        return solve(nums);
    }
};
main(){
    Solution ob;
    vector<int> v = {2,8,7,7,2};
    cout << (ob.reversePairs(v));
}

入力

{2,8,7,7,2}

出力

3

まとめ

この解法は、マージソートの分割統治の仕組みを活かし、マージの各段階でソート済みの二つの領域を線形時間で走査することにより、重要な逆ペアをすべて数え上げます。時間計算量は O(n log n)、追加メモリは O(n) であり、全ペアを調べる O(n²) の素朴な手法に比べて大幅に高速で、大きな入力にも十分対応できます。