C++で積が最小となるトリプレットの個数を数える方法

整数型の配列 Arr[] が与えられたとします。この記事のゴールは、考えられるすべてのトリプレット（三つ組）の中で「積」が最小になる組み合わせの個数を数えることです。具体的には、i < j < k を満たし、arr[i] * arr[j] * arr[k] が最小値となるトリプレットを対象にします。

解決の手順としては、まず i < j < k の条件下で実現可能な最小の積を求め、それを minprod として記録します。その後、積が minprod と一致するトリプレットをすべて数え上げます。

具体例で理解しよう

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

出力 − トリプレットの個数：2

説明 −

この配列における最小の積は 2 です。
トリプレット1 [ 1,2,3,2,4,1,5 ] → (1,2,1) 積 = 2
トリプレット2 [ 1,2,3,2,4,1,5 ] → (1,2,1) 積 = 2
最小の積 2 を持つトリプレットは合計 2 個です。

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

出力 − トリプレットの個数：1

説明 −

この配列における最小の積は 1 です。
トリプレット1 [ 1,1,2,1,2,2 ] → (1,1,1) 積 = 1
最小の積 1 を持つトリプレットは合計 1 個です。

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

• ランダムな値で初期化された整数型配列 Arr[] を用意します。
• 配列 Arr[] の長さを格納する変数 N を用意します。
• 関数 countTriplets(int arr[], int n) は、配列とその長さを引数に取り、積が最小積と一致するトリプレットの個数を返します。
• トリプレットの個数を数えるための変数 count を 0 で初期化します。
• 各トリプレットの積を保持する変数 prod を用意し、初期値は 1 とします。
• すべてのトリプレットの中で最小の積を保持する変数 minprod を用意し、初期値は十分大きな値（9999）とします。
• 3重の for ループを使って、トリプレットを構成する各要素を走査します。
• 外側のループは 0 ≤ i < n-2、内側のループは i < j < n-1、最も内側のループは j < k < n の範囲で動作します。
• prod = arr[i] * arr[j] * arr[k] を計算し、prod ≤ minprod であれば minprod を prod で更新します。
• この時点で、minprod にはすべてのトリプレットの中で最小の積が格納されています。
• 再度、3重の for ループを使って配列を走査します。
• ループの範囲は先ほどと同じく、0 ≤ i < n-2、i < j < n-1、j < k < n です。
• prod = arr[i] * arr[j] * arr[k] を計算し、prod == minprod であれば count をインクリメントします。これはそのトリプレットが最小の積を持つことを意味します。
• すべてのループが終了した時点で、count には条件を満たすトリプレットの総数が格納されています。
• count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n){
    int count = 0;
    int prod = 1;
    int minprod = 9999; // 配列内のどの積よりも大きい値で初期化
    for (int i = 0; i < n-2; i++){
        for (int j = i+1; j < n-1; j++){
            for (int k = j+1; k < n; k++){
                prod = arr[i]*arr[j]*arr[k];
                if ( prod <= minprod )
                    { minprod = prod; }
            }
        }
    }
    // cout<<"minproduct :"<<minprod; // 最小の積を表示する場合
    for (int i = 0; i < n-2; i++){
        for (int j = i+1; j < n-1; j++){
            for (int k = j+1; k < n; k++){
                prod = arr[i]*arr[j]*arr[k];
                if ( prod == minprod ){
                    count++;
                    // cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; // 表示する場合
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr[]={ 1,2,3,1,2,6};
    int N=5; // 配列の長さ
    cout << endl << "Number of triplets : " << countTriplets(Arr,N);
    return 0;
}

出力

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

Number of triplets : 2