【C++】3つの配列の要素からなる特別なトリプレットの合計を求める方法

この記事では、3つの配列 X、Y、Z が与えられたときに、それぞれの配列から1つずつ要素を選んで構成できる「特別なトリプレット」の合計値を求めるプログラムを紹介します。

特別なトリプレットとは？

特別なトリプレットとは、次の性質を満たす三つ組のことです。

(a, b, c)：a ≤ b かつ b ≥ c

つまり、トリプレットの中央にある要素 b が、両端の要素 a および c 以上でなければなりません。

そして、トリプレットの値は次の式で定義されます。

f(a, b, c) = (a+b) * (b+c)

具体例で理解しよう

入力：

X[] = {5, 9, 4} ; Y[] = {8, 6} ; Z[] = {7, 1}

すべての特別なトリプレットの値を実際に計算してみましょう。

(5, 8, 7) : 値 = (5+8) * (8+7) = 195
(5, 8, 1) : 値 = (5+8) * (8+1) = 117
(4, 8, 7) : 値 = (4+8) * (8+7) = 180
(4, 8, 1) : 値 = (4+8) * (8+1) = 108
(5, 6, 1) : 値 = (5+6) * (6+1) = 77
(4, 6, 1) : 値 = (4+6) * (6+1) = 70
特別なトリプレットの合計 = 747

なお、X の要素 9 は Y のどの要素よりも大きいため、「a ≤ b」という条件を満たす組み合わせが存在せず、どのトリプレットにも使えない点に注意してください。

解法1：全トリプレットを列挙するシンプルな方法

最も基本的なアプローチは、3つの配列から生成できるすべてのトリプレットを調べることです。各トリプレットが条件（a ≤ b かつ c ≤ b）を満たしているかを判定し、満たす場合のみ上記の式で値を計算して合計に加算していきます。

この方法を実装したプログラムがこちらです。

#include <iostream>
using namespace std;
int findSpecialTripletSum(int X[], int Y[], int Z[], int sizeX, int sizeY, int sizeZ) {
    int sum = 0;
    for (int i = 0; i < sizeX; i++) {
        for (int j = 0; j < sizeY; j++) {
            for (int k = 0; k < sizeZ; k++) {
                if (X[i] <= Y[j] && Z[k] <= Y[j])
                    sum = sum + (X[i] + Y[j]) * (Y[j] + Z[k]);
            }
        }
    }
    return sum;
}
int main() {
    int X[] = {5, 9, 4};
    int Y[] = {8, 6};
    int Z[] = {7, 1};
    int sizeX = sizeof(X) / sizeof(X[0]);
    int sizeY = sizeof(Y) / sizeof(Y[0]);
    int sizeZ = sizeof(Z) / sizeof(Z[0]);
    cout<<"Sum of special triplets = "<<findSpecialTripletSum(X, Y, Z,
    sizeX, sizeY, sizeZ);
}

出力：

Sum of special triplets = 747

解法2：ソートと累積和による効率的な方法

より効率の良い解法は、配列 X と Z をあらかじめ昇順にソートしておくことです。こうすることで、配列 Y の各要素について、二分探索（upper_bound）を使って条件を満たす要素の個数と合計を高速に求められるようになります。

配列 Y のインデックス i の要素を Y[i]、配列 X のうち Y[i] 以下の要素を {x1, x2}、配列 Z のうち Y[i] 以下の要素を {z1, z2} とすると、これらを使って構成できるトリプレットの値の総和 S は、次のように式変形できます。

S = (x1+Y[i])(Y[i]+z1) + (x1+Y[i])(Y[i]+z2) + (x2+Y[i])(Y[i]+z1) + (x2+Y[i])(Y[i]+z2)
S = (x1+Y[i])(2Y[i]+z1+z2) + (x2+Y[i])(2Y[i]+z1+z2)
S = (2Y[i] + x1 + x2)(2Y[i] + z1 + z2)

ここで、次の値を定義します。

• N：配列 X のうち Y[i] 以下の要素の個数
• M：配列 Z のうち Y[i] 以下の要素の個数
• Sx：配列 X のうち Y[i] 以下の要素の合計値
• Sz：配列 Z のうち Y[i] 以下の要素の合計値

これらを使うと、S は次のシンプルな式にまとめられます。

S = (N × Y[i] + Sx) × (M × Y[i] + Sz)

累積和（prefix sum）を事前に計算しておけば、各区間の合計も即座に取得できます。

上記の解法を実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
int tripletSumCalc(int X[], int Y[], int Z[], int prefixSumA[], int prefixSumC[], int sizeA, int sizeB, int sizeC){
    int totalSum = 0;
    for (int i = 0; i < sizeB; i++) {
        int currentElement = Y[i];
        int n = upper_bound(X, X + sizeA, currentElement) - X;
        int m = upper_bound(Z, Z + sizeC, currentElement) - Z;
        if (n == 0 || m == 0)
            continue;
        totalSum += ((prefixSumA[n - 1] + (n * currentElement)) * (prefixSumC[m - 1] + (m * currentElement)));
    }
    return totalSum;
}
int* findPrefixSum(int* arr, int n) {
    int* prefixSumArr = new int[n];
    prefixSumArr[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
    return prefixSumArr;
}
int findSpecialTripletSum(int A[], int B[], int C[], int sizeA, int sizeB, int sizeC){
    int specialTripletSum = 0;
    sort(A, A + sizeA);
    sort(C, C + sizeC);
    int* prefixSumA = findPrefixSum(A, sizeA);
    int* prefixSumC = findPrefixSum(C, sizeC);
    return tripletSumCalc(A, B, C, prefixSumA, prefixSumC, sizeA, sizeB, sizeC);
}
int main() {
    int A[] = {5, 9, 4};
    int B[] = {8, 6};
    int C[] = {7, 1};
    int sizeA = sizeof(A) / sizeof(A[0]);
    int sizeB = sizeof(B) / sizeof(B[0]);
    int sizeC = sizeof(C) / sizeof(C[0]);
    cout<<"Sum of special triplets = "<<findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
}

出力：

Sum of special triplets = 747

計算量の比較

解法1の時間計算量は O(|X|×|Y|×|Z|) となるため、配列が大きくなると処理時間が急激に増加します。一方、解法2ではソートに O(|X|log|X| + |Z|log|Z|)、メインのループ処理に O(|Y|×(log|X| + log|Z|)) 程度しかかからず、大規模なデータセットでも高速に動作します。実務的には、解法2の採用が推奨されます。