C++で配列から要素を削除して得られる最大ポイントを求める方法

概要

N個の要素を持つ配列Aと、2つの整数l、rが与えられます。ここで、各要素は 1 ≤ a_x ≤ 10⁵ を満たし、1 ≤ l ≤ r ≤ N という条件が成り立ちます。配列内の任意の要素（a_xとします）を選んで削除すると、同時に a_x+1、a_x+2 … a_x+R および a_x-1、a_x-2 … a_x-L に等しいすべての要素も配列から取り除くことができます。この操作を行うたびに a_x ポイントを獲得でき、目的は配列の全要素を削除し終えた時点での合計ポイントを最大化することです。

入力例1

2 1 2 3 2 2 1
l = 1, r = 1

出力例1

8

この例では、まず「2」を削除対象として選択します。すると、l=1、r=1 の範囲指定により、「(2−1)=1」と「(2+1)=3」も一緒に削除する必要があります。

この操作を繰り返して「2」を完全に取り除きます。したがって、合計ポイントは 2×4 = 8 となります。

入力例2

2 4 2 10 5
l = 1, r = 2

出力例2

19

この例では、まず「2」を削除し、次に「5」、最後に「10」を削除します。

合計ポイントは 2×2 + 5 + 10 = 19 となります。

解法のアプローチ

まず、配列内の全要素について出現回数を数えます。ある要素Xを選んだ場合、範囲 [X−l, X+r] 内のすべての要素が削除されることになります。ここで、l と r のうち小さい方の範囲を採用し、要素Xを選んだときにどの要素まで削除されるのかを決定します。

その結果は、「それまでに削除済みの要素から得られる最大値」と「要素Xを削除した場合に得られる値」のうち大きい方となります。この計算には動的計画法（DP）を活用し、以前に削除した要素の結果を保存しながら処理を進めることで、効率的に最大値を求められます。

C++実装例

// 配列からすべての要素を削除した後に
// 得られる最大コストを求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 最大コストを返す関数
int maxCost(int a[], int m, int L, int R){
    int mx1 = 0, k1;
    // 配列の最大要素を求める
    for (int p = 0; p < m; ++p)
        mx1 = max(mx1, a[p]);
    // 全要素の出現回数をゼロで初期化
    int count1[mx1 + 1];
    memset(count1, 0, sizeof(count1));
    // 配列内の全要素の出現頻度を計算
    for (int p = 0; p < m; p++)
        count1[a[p]]++;
    // 削除済み要素のコストを格納する配列
    int res1[mx1 + 1];
    res1[0] = 0;
    // L と R のうち小さい方の範囲を採用
    L = min(L, R);
    for (int num1 = 1; num1 <= mx1; num1++) {
        // 要素 num を選択した際に、
        // どの要素まで削除されるかを決定
        k1 = max(num1 - L - 1, 0);
        // 要素 num を選ぶ場合と選ばない場合の
        // 大きい方を取得
        res1[num1] = max(res1[num1 - 1], num1 * count1[num1] +
        res1[k1]);
    }
    return res1[mx1];
}

// ドライバープログラム
int main(){
    int a1[] = { 1, 1, 3, 3, 3, 2, 4 }, l1 = 1, r1 = 1;
    int a2[] = { 2, 4, 2, 10, 5 }, l2 = 1, r2 = 2;
    // 配列のサイズ
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int n2 = sizeof(a2) / sizeof(a2[0]);
    // 最大コストを求める関数呼び出し
    cout<<"Maximum Cost for First Example:" << maxCost(a1, n1, l1,r1)<<endl;
    cout<<"Maximum Cost for Second Example:" << maxCost(a2, n2, l2,r2);
    return 0;
}

実行結果

Maximum Cost for First Example:11
Maximum Cost for Second Example:19

まとめ

本記事では、配列の要素を削除する際に連鎖的に関連要素も取り除き、獲得できる合計ポイントを最大化する問題を扱いました。要素の出現頻度を記録し、動的計画法によって各値における最適な選択を累積的に求めることで、O(N + M) の計算量で効率的に答えを導き出せます。類似の頻度集計＋DPのパターンは他の競技プログラミング問題にも応用できるため、ぜひ理解を深めておきましょう。