C++で解く「削除して獲得する（Delete and Earn）」問題の解法

問題の概要

整数型の配列 nums が与えられ、この配列に対して複数回の操作を行うことを考えます。各操作では、任意の nums[i] を 1 つ選んで削除し、その値に等しいポイント nums[i] を獲得できます。ただし重要なルールとして、nums[i] - 1 または nums[i] + 1 に等しい要素はすべて同時に削除しなければなりません。初期時点のポイントは 0 です。これらの操作を適用したときに獲得できるポイントの最大値を求めるのがこの問題です。

たとえば、入力が [3, 4, 2] の場合、出力は 6 になります。理由は次のとおりです。まず 4 を削除すると 4 ポイントを獲得でき、同時に隣接する値である 3 も削除されます。続いて残った 2 を削除すれば 2 ポイントを獲得できます。合計で 6 ポイントとなり、これが最大です。

解法のアプローチ

この問題は動的計画法（DP）によって効率的に解けます。ポイントとなるのは、同じ値の要素は一度にまとめて処理できるという点です。そこで、各値の出現回数を std::map に記録します。map はキー順に自動的にソートされるため、値の小さいものから順に処理を進められます。各値について「その値を選ぶ場合の累積ポイント」と「選ばない場合の累積ポイント」を比較しながら最適解を更新していきます。構造としては、有名な「家を襲う（House Robber）」問題と同じ考え方です。

具体的な手順は以下のとおりです。

• n を nums のサイズとし、map 型の変数 m を定義、答えとなる ret を 0 で初期化します。nums 内の各要素の出現頻度を m に格納します。

• カウンタ cnt を 0 で初期化します。

• m の各ペア it に対して以下を繰り返します。

  • x := it のキー（現在の値）

  • temp := x × it の値（出現回数）。現在の値をすべて取得した場合のポイント

  • it1 := it の直前の要素、it2 := it1 の直前の要素を指すイテレータ

  • cnt ≥ 1 かつ x − it1 のキー > 1 の場合：直前の値と隣接していないため、temp に m[it1 のキー] を加算できます

  • それ以外で cnt ≥ 2 の場合：直前の値と隣接しているため両方は取れず、temp に m[it2 のキー] を加算します

  • a := cnt ≥ 1 なら m[it1 のキー]、そうでなければ 0（現在の値を選ばない場合のポイント）

  • m[it のキー] := max(temp, a)

  • ret := max(ret, temp)

  • cnt を 1 増やします

• 最後に ret を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        map <int, int> m;
        int ret = 0;
        for(int i = 0; i < nums.size(); i++){
            m[nums[i]]++;
        }
        int cnt = 0;
        map <int, int> :: iterator it = m.begin();
        while(it != m.end()){
            int x = it->first;
            int temp = x * it->second;
            map <int, int> :: iterator it1 = prev(it);
            map <int, int> :: iterator it2 = prev(it1);
            if(cnt >= 1 && x - it1->first > 1){
                temp += m[it1->first];
            }
            else if(cnt >= 2){
                temp += m[it2->first];
            }
            m[it->first] = max(temp, cnt >= 1 ? m[it1->first] : 0);
            ret = max(ret, temp);
            it++;
            cnt++;
        }
        return ret;
    }
};
main(){
    vector<int> v = {3,4,2};
    Solution ob;
    cout << (ob.deleteAndEarn(v));
}

入力

[3,4,2]

出力

6

計算量の目安

時間計算量は O(n log n) です。map への要素挿入と走査にそれぞれ対数時間がかかるためです。空間計算量は O(n) となり、ユニークな値の数だけ map にエントリが保持されます。配列をソートして処理する方式でも同様の結果が得られますが、map を使うことで重複値の集計とソートを同時に扱えるのが利点です。