C++でi < jとなる一意なペア（arr[i], arr[j]）の個数を求める方法

問題概要

整数要素を含む配列が与えられたとき、ペア (arr[i], arr[j]) のインデックスが i < j を満たすような、一意なペアの個数を求めるのが本記事のゴールです。

具体例を使って理解していきましょう。

入力 − arr[] = {1,2,3};

出力 − i < j を満たす一意なペア (arr[i], arr[j]) の個数 − 3

説明 − すべての要素が一意であるため、ペアは以下のようになります。

(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2

入力 − arr[] = { 4,4,3,2};

出力 − i < j を満たす一意なペア (arr[i], arr[j]) の個数 − 4

説明 − 同じ値の組み合わせは一度だけカウントされます。ペアは以下のようになります。

(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3

解法1：素朴なアプローチ（ナイーブ法）

まずはforループを使ったシンプルな方法から見ていきます。2つのforループで配列 arr[] を走査します。外側のループは i=0 から i<length-1 まで、内側のループは j=i+1 から j<length までとすることで、常に i < j が保証されます。そして、ペア (arr[i], arr[j]) を set<pair<int, int>> 型の変数 se に追加していきます。最終的な se のサイズが、i < j を満たす一意なペアの個数となります。

• 整数要素を持つ配列 arr[] とその長さ size を用意します。

• 関数 unique_pair(int arr[], int size) は配列とその長さを受け取り、ペア (arr[i], arr[j]) において i < j となる一意なペアの数を返します。

• count の初期値を 0 とします。

• 整数ペアを格納するセット se（set<pair<int, int>>）を用意します。

• 2つのforループで arr[] を走査します。i は 0 から size-1 未満まで、j は i+1 から size 未満までです。

• 常に i < j となるため、se.insert(make_pair(arr[i], arr[j])) によって各ペアを se に挿入します。

• 両方のループが完了したら、count = se.size() と更新します。

• これで count には se 内のペアの数（すべて一意）が格納されます。

• count を結果として返します。

解法2：効率的なアプローチ

この手法では、各要素より後ろに存在する一意な要素を調べます。arr[i] は、arr[i+1] から arr[size-1] までの範囲に含まれる一意な要素とペアを組みます。つまり、arr[i] の後ろに x 個の一意な要素があれば、arr[i] は x 個のペアを作れるということです。そこで、まず「あるインデックス i より後ろにいくつ一意な要素があるか」を記録した配列を作成し、それぞれのカウントを合計して一意なペアの総数を求めます。

• 整数要素を持つ配列 arr[] とその長さ size を用意します。

• 関数 unique_pair(int arr[], int size) は配列とその長さを受け取り、ペア (arr[i], arr[j]) において i < j となる一意なペアの数を返します。

• count の初期値を 0 とします。

• 一時変数 temp を 0 で初期化します。

• 長さ size の配列 arr_2[] を用意し、arr_2[size-1] = 0 と初期化します（最後の要素の後ろに一意な要素は存在しないため）。

• 2つの整数セット check と uncheck を作成します。

• 配列を末尾から先頭に向かって走査します（i = size-1 から i ≥ 0）。check セット内に arr[i] が存在するか検索します。

• 見つからなければ一意な要素なので temp をインクリメントし、arr_2[i] = temp とします。

• 見つかった場合は temp を増やさずに arr_2[i] = temp とします。

• arr[i] を check セットに挿入します。これにより、以降に出現する同じ値は一意とはみなされなくなります。

• このforループが終了すると、arr_2[] の更新が完了します。

• 次に、配列 arr[] をインデックス i = 0 から i < size-1 まで走査します。各 arr[i] について uncheck セット内を確認し、存在しなければ初めての出現なので、count に arr_2[i]（arr[i] の後ろにある一意な要素数）を加算します。存在する場合は何もせず次へ進みます。

• arr[i] を uncheck セットに挿入します。これにより、以降に出現する同じ値が二重にカウントされることはありません。

• 最終的に count には、i < j を満たす一意なペア (arr[i], arr[j]) の数が格納されています。

• count を結果として返します。

実装例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
    int count = 0;
    set<pair<int, int>> se;
    for(int i = 0; i < (size - 1); i++){
        for (int j = i + 1; j < size; j++){
            se.insert(make_pair(arr[i], arr[j]));
        }
    }
    count = se.size();
    return count;
}
int main(){
    int arr[] = { 4, 3, 1, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10

実装例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
    int count = 0, temp = 0;
    int arr_2[size];
    arr_2[size-1] = 0;
    set<int> check, uncheck;
    for (int i = size - 1; i > 0; i--){
        auto set = check.find(arr[i]);
        if (set != check.end()){
            arr_2[i - 1] = temp;
        }
        else{
            arr_2[i - 1] = ++temp;
        }
        check.insert(arr[i]);
    }
    for (int i = 0; i < size - 1; i++){
        auto set = uncheck.find(arr[i]);
        if (set != uncheck.end()){
            continue;
        }
        count += arr_2[i];
        uncheck.insert(arr[i]);
    }
    return count;
}
int main(){
    int arr[] = { 4, 3, 1, 6, 7 };
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10

まとめ

素朴なアプローチは実装が非常にシンプルですが、すべてのペア候補を生成するため計算量は O(n²) 程度になります。一方、効率的なアプローチはセットを活用して各要素以降の一意な要素数を前計算するため、O(n log n) で処理可能です。大きなサイズの配列を扱う場合は、効率的なアプローチを選ぶことでパフォーマンスを大幅に改善できます。