C++で合計が指定値xに等しい4つの配列からなる4つ組（クアドラプル）を数える方法

4つの配列 A[]、B[]、C[]、D[] が与えられたとき、A[i]+B[j]+C[k]+D[l] = x を満たす要素の組み合わせ（4つ組）がいくつ存在するかを求めるのが本記事の目的です。4つの配列はいずれも同じ要素数 N を持つものとします。

解き方はシンプルです。各配列を順に走査しながら、A[i]+B[j]+C[k]+D[l] が x と等しいかどうかを1つずつ確認し、条件を満たす組み合わせが見つかるたびにカウントを増やしていきます。

具体例で理解しましょう。

入力例1

A[]={ 1,2,3}; B[]={ 2,3,2}; C[]={ 4,3,1}; D[]={ 3,1,1 }; X=12

出力例1

4つ組の数: 4

説明

条件を満たす組み合わせ ( A[i] B[j] C[k] D[l] ) は以下の通りです。

(2 3 4 3), (3 2 4 3), (3 3 3 3), (3 2 4 3)

よって、合計が12となる4つ組は4個となります。

入力例2

A[]={ 1,1,1}; B[]={ 2,2,2}; C[]={ 3,3,3}; D[]={ 4,4,4 }; X=15

出力例2

4つ組の数: 0

説明

合計が15になる要素の組み合わせは存在しません。実際、各配列の最大値を組み合わせても 4+4+4+4=16 に対し、この例では 1+2+3+4=10 が最大のため、該当する組み合わせは0個となります。

プログラムで使用するアプローチ

• 同じ長さの整数配列 A[]、B[]、C[]、D[] を用意し、数値で初期化します。

• 配列の長さを格納する変数 N を用意します。

• 関数 countQuads(int a[], int b[], int c[], int d[], int x, int n) は、4つの配列と共通の長さ n、目標値 x を引数に受け取り、条件を満たす組み合わせの数を返します。

• 各配列に対して4重のループで走査を行います。

• 最も外側のループは a[] 用の 0<=i<n、その内側に b[] 用の 0<=j<n、続いて c[] 用の 0<=k<n、最も内側に d[] 用の 0<=l<n を配置します。

• a[i]+b[j]+c[k]+d[l]==x が成り立つかどうかを比較し、真であればカウントを増やします。

• すべてのループが終了した時点で、count には合計が x となる4つ組の個数が格納されています。

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

なお、この方法はすべての組み合わせを調べる全探索（ブルートフォース）であり、計算量は O(N⁴) となります。配列のサイズが大きい場合には、ハッシュマップを利用した O(N²) の最適化手法も検討するとよいでしょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int countQuads(int a[],int b[],int c[],int d[],int x, int n){
    int count = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                for (int l = 0; l < n; l++){
                    int sum=a[i]+b[j]+c[k]+d[l];
                    if(sum==x){
                        count++;
                        cout<<endl<<a[i]<<" "<<b[j]<<" "<<c[k]<<" "<<d[l];}
                    }
                }
            }
        }
    return count;
}
int main(){
    int A[]={ 1,1,1}; int B[]={ 2,2,2}; int C[]={ 3,3,3}; int D[]={ 4,4,4 };
    int X=15;
    int N=3; //各配列の長さ
    cout <<endl<< "4つ組の数 : "<<countQuads(A,B,C,D,X,N);
    return 0;
}

出力

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

4つ組の数 : 0