C++で指定された合計値となる4つ組の個数を求める方法

問題概要

4つの整数型配列が与えられます。それぞれの配列から1つずつ要素を選んで作られる「4つ組（クアドラプレット）」のうち、その合計が指定された値（Sum）と一致するものが何通りあるかを求めるのが目的です。ポイントは、選んだ4つの要素が必ず異なる配列に属していなければならないという点です。

最もシンプルな解法は、4重のforループですべての組み合わせを走査し、A[i] + B[j] + C[k] + D[l] == sum が成立するたびにカウントを増やしていく全探索です。

入出力例

例1

入力：

A[]={ 1,3,1 }, B[]={ 2,4,5 }, C[]={ 1,1,2 }, D[]={ 4,4,0 }、Sum=5

出力： 条件を満たす4つ組の個数：2

説明：

該当する2つの4つ組は以下の通りです。
(A[0],B[0],C[2],D[2]) → (1,2,2,0)、合計=5
(A[2],B[0],C[2],D[2]) → (1,2,2,0)、合計=5

例2

入力：

A[]={ 1,1,1 }, B[]={ 1,1,1 }, C[]={ 1,1,1 }, D[]={ 1,1,1 }、Sum=3

出力： 条件を満たす4つ組の個数：0

説明： どの組み合わせを選んでも合計は4となり、3より大きいため条件を満たす4つ組は存在しません。

アルゴリズムの考え方

• 同じ長さの整数型配列 first[]、second[]、third[]、fourth[] を用意します。
• 各配列の長さを格納する変数 first_size、second_size、third_size、fourth_size を用意します。
• 目標となる合計値を格納する変数 sum を用意します。
• 関数 quadruplets() は、4つの配列・それぞれの長さ・合計値を受け取り、条件を満たす4つ組の個数を返します。
• forループで各配列を順に走査します。最も外側のループは first[] 用の 0<=i<first_size、続いて second[] 用の 0<=j<second_size、third[] 用の 0<=k<third_size、最も内側に fourth[] 用の 0<=l<fourth_size を配置します。
• first[i] + second[j] + third[k] + fourth[l] == sum が成り立てば、カウントを1増やします。
• すべてのループが終了した時点で、count には条件を満たす4つ組の総数が格納されています。
• count を結果として返します。

なお、この手法の計算量は各配列のサイズを n とすると O(n⁴) となります。配列が小さい場合は十分実用的ですが、大規模なデータに対してはハッシュマップなどを活用した高速化を検討するとよいでしょう。

C++実装例

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

int quadruplets(int first[], int second[], int third[], int fourth[],
                int first_size, int second_size, int third_size, int fourth_size, int sum){
    int count = 0;
    for (int i = 0; i < first_size; i++){
        for (int j = 0; j < second_size; j++){
            for (int k = 0; k < third_size; k++){
                for (int l = 0; l < fourth_size; l++){
                    if (first[i] + second[j] + third[k] + fourth[l] == sum){
                        count++;
                    }
                }
            }
        }
    }
    return count;
}

int main(){
    int first[] = { 7, -8 };
    int second[] = { 7, -2 };
    int third[] = { 4, -2 };
    int fourth[] = { 3, -4 };
    int first_size = sizeof(first) / sizeof(first[0]);
    int second_size = sizeof(second) / sizeof(second[0]);
    int third_size = sizeof(third) / sizeof(third[0]);
    int fourth_size = sizeof(fourth) / sizeof(fourth[0]);
    int sum = 0;
    cout << "Count of quadruplets with given sum are: "
         << quadruplets(first, second, third, fourth,
                       first_size, second_size, third_size, fourth_size, sum);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

Count of quadruplets with given sum are: 1

この例では、(-8) + 7 + (-2) + 3 = 0 となる組み合わせが1通りだけ存在するため、結果は 1 となります。