C++で解く「最後の石の重み II」：動的計画法による効率的な解法

問題概要

正の整数の重みを持つ石が複数与えられます。各ターンごとに、任意の2つの石を選んで衝突させます。2つの石の重みをそれぞれ x と y（x ≤ y）としたとき、衝突の結果は以下のようになります。

• x = y の場合：両方の石は完全に砕けて消滅します。
• x ≠ y の場合：重み x の石は完全に破壊され、重み y の石は新しい重み y − x となります。

最終的に残る石は高々1つです。このとき、残った石の重みとして可能な最小値を求めてください（すべての石が消滅した場合は 0 とします）。

入力例と実行手順

たとえば入力が [2,7,4,1,8,1] の場合、出力は 1 になります。具体的な手順は次の通りです。

• (2, 4) を衝突させる → 配列は [2,7,1,8,1] になる
• (7, 8) を衝突させる → 配列は [2,1,1,1] になる
• (2, 1) を衝突させる → 配列は [1,1,1] になる
• (1, 1) を衝突させる → 最後に残るのは 1 のみ

解法のポイント：部分和問題への帰着

この問題は、単純なシミュレーションでは非効率ですが、「石を2つのグループに分けるとどうなるか」という視点で考えると動的計画法（DP）で解けます。

石をグループ A とグループ B に分けたとき、衝突操作を繰り返して最終的に残る重みは |sum(A) − sum(B)| に等しくなります。したがって、合計の半分（total / 2）以下で実現できる最大の部分和を見つければ、答えは「total − 2 × その部分和」となります。これは典型的な 0/1 ナップサック型の DP で求められます。

アルゴリズムの手順

• n を石の配列のサイズとし、total := 0 で初期化する
• i を 0 から n − 1 まで回し、total に stones[i] を加算して総和を求める
• req := total / 2 とする（目標とする部分和の上限）
• サイズ req + 1 のブール型配列 dp を用意し、すべて false で初期化する
• dp[0] := true とし、reach := 0 で初期化する
• i を 0 から n − 1 まで繰り返す
  • j を req から開始し、j − stones[i] ≥ 0 を満たす間、j を 1 ずつ減らしながら以下を実行する
    • dp[j] = dp[j] || dp[j − stones[i]] で更新する
    • dp[j] が true であれば、reach = max(reach, j) で更新する
• total − 2 × reach を返す

ここで dp[j] は「いくつかの石を選んで重みの合計をちょうど j にできるか」を表します。内側のループを大きい j から小さい j へ向かって処理することで、同じ石を二度使うことを防いでいます。これは 0/1 ナップサック DP の定番テクニックです。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int total = 0;
        for(int i = 0; i < n; i++){
            total += stones[i];
        }
        int req = total / 2;
        vector<bool> dp(req + 1, false);
        dp[0] = true;
        int reach = 0;
        for(int i = 0; i < n; i++){
            for(int j = req; j - stones[i] >= 0; j--){
                dp[j] = dp[j] || dp[j - stones[i]];
                if(dp[j]) reach = max(reach, j);
            }
        }
        return total - (2 * reach);
    }
};
main(){
    vector<int> v = {2,7,4,1,8,1};
    Solution ob;
    cout << (ob.lastStoneWeightII(v));
}

入力

[2,7,4,1,8,1]

出力

1

計算量

時間計算量は O(n × total / 2)、空間計算量は O(total / 2) です。ここで n は石の個数、total は石の重みの合計を表します。石の総重量がそれほど大きくなければ、非常に効率的に解ける問題です。