【C++解説】繰り返し要素の頻度の合計が2×k以下という条件下で配列から最大積を求める方法

このチュートリアルでは、「積に含まれるすべての繰り返し要素の出現回数(頻度)の合計が 2 × k 以下である」という制約のもとで、配列から達成できる最大の積を求めるプログラムについて解説します。

問題の概要

整数の配列と整数 k が与えられます。積を構成する要素の中に同じ数字が複数回現れる場合、それらの繰り返し回数の合計が 2 × k を超えてはならないという条件を満たしながら、配列から作れる最大の積を求めるのが課題です。

アルゴリズムの考え方

この問題は、ソートとハッシュマップを組み合わせることで効率的に解くことができます。手順は以下の通りです。

1. 配列を昇順にソートします。
2. ハッシュマップ(unordered_map)を使って各要素の出現回数を記録します。まだ一度も現れていない要素(初登場の要素)だけを積に掛け合わせます。
3. ソート済み配列を大きい方から走査し、重複して現れた要素について、残っている予算 k の範囲内で追加の分を積に掛け合わせます。
4. 予算 k を使い切った時点で処理を打ち切り、最終的な積を結果として返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// 最大の積を返す関数
ll maxProd(int arr[], int n, int k) {
    ll product = 1;
    unordered_map<int, int> s;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (s[arr[i]] == 0) {
            product = product * arr[i];
        }
        // ハッシュマップに出現回数を記録
        s[arr[i]] = s[arr[i]] + 1;
    }
    for (int j = n - 1; j >= 0 && k > 0; j--) {
        if ((k > (s[arr[j]] - 1)) && ((s[arr[j]] - 1) > 0)){
            product *= pow(arr[j], s[arr[j]] - 1);
            k = k - s[arr[j]] + 1;
            s[arr[j]] = 0;
        }
        if (k <= (s[arr[j]] - 1) && ((s[arr[j]] - 1) > 0)) {
            product *= pow(arr[j], k);
            break;
        }
    }
    return product;
}
int main() {
    int arr[] = { 5, 6, 7, 8, 2, 5, 6, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxProd(arr, n, k);
    return 0;
}

出力

161280

動作の解説

サンプルコードでは、配列 { 5, 6, 7, 8, 2, 5, 6, 8 } と k = 2 を使用しています。処理の流れは以下のようになります。

1. まず、それぞれ一意な要素である 5, 6, 7, 8, 2 を掛け合わせ、この時点で積は 3360 になります。
2. 続いて大きい方から重複要素を確認すると、最初は 8 の重複分(あと 1 個)です。これを積に掛け合わせると予算は 2 → 1 となり、積は 26880 になります。
3. 次の 6 の重複分については残り予算が 1 しかないため、6 を 1 個だけ追加で掛け合わせて処理を終了します。最終的な積は 161280 です。

計算量

ソートに O(n log n)、その後のハッシュマップへの出現回数の記録および走査に O(n) の計算量がかかるため、アルゴリズム全体の時間計算量は O(n log n) となります。