概要

各宝石について「持ち込まない」「通常の重さで持ち込む」「軽量化ケースを使って持ち込む」のいずれかを選び、総重量が \(C\) 以下になるように価値の合計を最大化する問題です。

これは「使った軽量化ケースの個数」も状態に持つ 0/1 ナップサック DP で解くことができます。

考察

各宝石は最大 1 つまでしか持ち込めません。また、軽量化ケースを使う場合も同じ宝石に複数個使うことはできません。

宝石 \(i\) に対して選択肢は次の 3 通りです。

1. 持ち込まない
2. 通常の重さ \(W_i\) で持ち込む
3. 軽量化ケースを 1 個使い、重さ \(\lfloor W_i / 2 \rfloor\) で持ち込む

素朴に全ての選び方を試すと、各宝石について最大 3 通りの選択があるため、\(O(3^N)\) のような膨大な計算量になってしまい、\(N \leq 10^5\) では到底間に合いません。

通常の 0/1 ナップサックでは「現在の重さ」だけを状態に持ちますが、この問題では軽量化ケースの使用個数に上限 \(K\) があります。
そのため、「重さ」に加えて「何個のケースを使ったか」も DP の状態として管理する必要があります。

そこで、次のような DP を考えます。

\(dp[k][w] =\) 軽量化ケースを \(k\) 個使い、総重量がちょうど \(w\) のときの価値の最大値

到達不可能な状態は十分小さい値で初期化します。

宝石を 1 つずつ見ていき、各宝石について

• 通常の重さで追加する
• 軽量化して追加する

という遷移を行います。

アルゴリズム

DP 配列を次のように定義します。

\[ dp[k][w] = \text{軽量化ケースを } k \text{ 個使い、総重量 } w \text{ のときの価値の最大値} \]

初期状態は、何も選んでいない状態なので

\[ dp[0][0] = 0 \]

とします。それ以外の状態は到達不可能として、十分小さい値で初期化します。

各宝石 \((B_i, W_i)\) について、軽量化したときの重さを

\[ \left\lfloor \frac{W_i}{2} \right\rfloor \]

とします。

現在の状態が \(dp[k][w]\) のとき、次の遷移を行います。

1. 通常の重さで持ち込む

重さが \(W_i\) 増え、価値が \(B_i\) 増えます。

\[ dp[k][w + W_i] = \max(dp[k][w + W_i], dp[k][w] + B_i) \]

ただし、\(w + W_i \leq C\) の場合のみです。

2. 軽量化ケースを使って持ち込む

ケースを 1 個使い、重さが \(\lfloor W_i / 2 \rfloor\) 増え、価値が \(B_i\) 増えます。

\[ dp[k + 1][w + \lfloor W_i / 2 \rfloor] = \max(dp[k + 1][w + \lfloor W_i / 2 \rfloor], dp[k][w] + B_i) \]

ただし、\(k + 1 \leq K\) かつ \(w + \lfloor W_i / 2 \rfloor \leq C\) の場合のみです。

逆順にループする理由

各宝石は最大 1 回しか選べません。

そのため、同じ宝石を DP の更新中に複数回使ってしまわないように、\(k\) と \(w\) を大きい方から小さい方へ逆順に走査します。

for (int k = K; k >= 0; k--) {
    for (int w = C; w >= 0; w--) {
        ...
    }
}

これにより、今処理している宝石で更新された状態を、同じ宝石の処理中に再び使ってしまうことを防げます。

最後に、重量は \(C\) 以下であればよく、ケースも \(K\) 個以下であればよいので、全ての \(dp[k][w]\) の最大値を答えにします。

\[ \max_{0 \leq k \leq K,\ 0 \leq w \leq C} dp[k][w] \]

計算量

• 時間計算量: \(O(NKC)\)
• 空間計算量: \(O(KC)\)

制約で

\[ N(K+1)(C+1) \leq 2 \times 10^7 \]

が保証されているため、この計算量で十分間に合います。

実装のポイント

DP の値は価値の合計なので、最大でかなり大きくなります。
\(B_i \leq 10^9\) かつ \(N\) が大きいため、int ではなく long long を使います。

また、到達不可能な状態を表すために、十分小さい値 NEG を用意します。

const long long NEG = -(1LL << 60);

遷移前には、その状態が到達可能かどうかを確認します。

if (dp[k][w] == NEG) continue;

最後に、ケースを必ず \(K\) 個使う必要はなく、重量も必ず \(C\) ぴったりにする必要はありません。
そのため、全ての \(k \leq K\)、\(w \leq C\) について最大値を取る必要があります。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, C, K;
    cin >> N >> C >> K;

    const long long NEG = -(1LL << 60);
    vector<vector<long long>> dp(K + 1, vector<long long>(C + 1, NEG));
    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        long long B;
        int W;
        cin >> B >> W;

        int halfW = W / 2;

        for (int k = K; k >= 0; k--) {
            for (int w = C; w >= 0; w--) {
                if (dp[k][w] == NEG) continue;

                if (w + W <= C) {
                    dp[k][w + W] = max(dp[k][w + W], dp[k][w] + B);
                }

                if (k + 1 <= K && w + halfW <= C) {
                    dp[k + 1][w + halfW] = max(dp[k + 1][w + halfW], dp[k][w] + B);
                }
            }
        }
    }

    long long ans = 0;
    for (int k = 0; k <= K; k++) {
        for (int w = 0; w <= C; w++) {
            ans = max(ans, dp[k][w]);
        }
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。