【C++】アクセスするたびに最大値が1ずつ減少する配列から最大値の合計を求める方法

問題の概要

この問題では、N個の整数からなる配列 arr[] と整数 m が与えられます。求めるのは、「最大値にアクセスするたびにその値が1減少する」という条件下で、配列から取り出せる最大値の合計です。

問題の説明

配列の最大要素を取り出して合計（maxSum）に加算し、取り出した最大値を1減らす――この操作をm回繰り返したときの最終的なmaxSumを求めます。

具体的な例で理解しよう

入力例

arr[] = {3, 6, 7, 8, 8}, m = 3

出力例

23

処理の流れ

1回目: 処理前 {3, 6, 7, 8, 8} → 最大値 = 8、合計 = 8、処理後 {3, 6, 7, 7, 8}
2回目: 処理前 {3, 6, 7, 7, 8} → 最大値 = 8、合計 = 16、処理後 {3, 6, 7, 7, 7}
3回目: 処理前 {3, 6, 7, 7, 7} → 最大値 = 7、合計 = 23、処理後 {3, 6, 6, 7, 7}
最大合計 = 23

解決アプローチ

基本のアイデアはシンプルです。配列の最大値を求め、それをmaxSumに加算した後、該当する値を1減らします。この処理をm回繰り返せば答えが得られます。

最大要素を毎回効率よく取り出すには、最大ヒープ（priority_queue）データ構造を使うのが最も効果的です。

まず配列の全要素を最大ヒープに挿入します。最大ヒープでは最大値が常に根（ルート）に配置されるため、ルートを取り出してmaxSumに加算し、代わりに「取り出した値 − 1」をヒープへ戻します。これをm回繰り返すことで、目的のmaxSumが求まります。

アルゴリズム

初期化： maxSum = 0

1. ステップ1: 最大ヒープを作成し、配列の要素をすべてプッシュする。
2. ステップ2: i が 0 から m−1 までの間、ステップ3〜5を繰り返す。
3. ステップ3: ルート要素を maxVal として取得し、ヒープから取り除く（pop）。
4. ステップ4: maxVal を maxSum に加算する（maxSum += maxVal）。
5. ステップ5: 更新後の値（maxVal − 1）をヒープに戻す（push）。
6. ステップ6: ループ終了後、maxSum を返す。

C++での実装例

以下は、この解法の動作を示すプログラムです。

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

// アクセスごとに最大値を1減らしながら、m回分の合計を計算する関数
long calcMaxSumDec(int arr[], int m, int n) {
    long maxSum = 0;
    long maxVal;
    priority_queue<long> max_heap; // 最大ヒープ
    for (int i = 0; i < n; i++) {
        max_heap.push(arr[i]);
    }
    for (int i = 0; i < m; i++) {
        maxVal = max_heap.top();   // 現在の最大値を取得
        maxSum += maxVal;
        max_heap.pop();
        max_heap.push(maxVal - 1); // 1減らして戻す
    }
    return maxSum;
}
int main() {
    int arr[] = { 2, 3, 5, 4 }, m = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "アクセスごとに最大値が減少するときの最大値の合計は " << calcMaxSumDec(arr, m, n);
}

実行結果

アクセスごとに最大値が減少するときの最大値の合計は 13

計算量の評価

ヒープの構築に O(n log n)、各アクセスごとに1回の取り出しと挿入で O(log n) がm回分必要です。したがって全体の時間計算量は O((n + m) log n)、空間計算量は O(n) となります。

まとめ

最大ヒープ（priority_queue）を活用すれば、「アクセスするたびに最大値が減少する」タイプの問題をシンプルかつ効率的に解くことができます。「上位K個の要素を繰り返し取り出す」形式の多くの競技プログラミング問題でも応用できる重要なテクニックなので、ぜひマスターしておきましょう。