C++で最大の幾何平均を持つサブセットを検索する方法

問題の概要

ここでは、複数の要素を含む配列 A が与えられ、その中から幾何平均が最大となるサブセットを見つけることが課題となります。

例として、A = [1, 5, 7, 2, 0] という配列を考えてみましょう。この場合、最大の幾何平均を持つサブセットは [5, 7] になります。

解法のアプローチ

この問題には便利な性質があります。すべての要素が正の数である場合、配列内で最も大きい2つの要素を選べば、それらの組み合わせが必ず最大の幾何平均を持つことが数学的に保証されています。これは、幾何平均は要素の積の n 乗根であり、正の数同士では要素数が増えるほど（1より大きい値のみなら別ですが）平均が引き下げられる可能性があるためです。

したがって、幾何平均を実際に計算する必要はなく、以下の手順で解くことができます。

• 配列を1回走査して、最大値と2番目に大きい値を求める
• その2つの値をサブセットとして出力する

この方法なら、計算量はわずか O(n)、追加のメモリも不要（O(1)）で非常に効率的です。

C++での実装例

#include <iostream>
using namespace std;

void largestGeoMeanSubset(int arr[], int n) {
    // 要素が2つ未満の場合はサブセットを作れない
    if (n < 2) {
        cout << "Very few number of elements";
        return;
    }

    int max = INT_MIN, second_max = INT_MIN;

    // 1回の走査で最大値と2番目に大きい値を求める
    for (int i = 0; i < n; i++) {
        if (arr[i] > max) {
            second_max = max;
            max = arr[i];
        } else if (arr[i] > second_max) {
            second_max = arr[i];
        }
    }

    cout << second_max << ", " << max;
}

int main() {
    int arr[] = {1, 5, 7, 2, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    largestGeoMeanSubset(arr, n);
}

出力結果

5, 7

コードの解説

このプログラムの動作を順に見ていきましょう。

1. 要素数のチェック： 要素が2つ未満の場合、サブセットを構成できないためメッセージを表示して終了します。
2. 変数の初期化： 最大値を格納する max と、2番目に大きい値を格納する second_max を INT_MIN で初期化します。
3. 1回の走査： 各要素について、現在の最大値より大きければ max を更新し、元の max の値を second_max へ繰り下げます。最大値より小さくても second_max より大きい場合は second_max を更新します。
4. 結果の出力： 見つかった2つの値を出力します。サンプル配列 {1, 5, 7, 2, 0} では、最大値 7 と2番目に大きい値 5 が検出され、「5, 7」が出力されます。

注意点

この手法はすべての要素が正の数（または非負）である場合に有効です。負の数やゼロが含まれる配列では、幾何平均の挙動が変わるため、別途ケース分けが必要になる点に留意してください。