概要

この問題は、制限重量 \(C\) のナップサック問題に、「最大 \(K\) 個の宝石の重さを半分（端数切り捨て）にできる」という特別なルールが加わった、動的計画法（DP）の応用問題です。

---

考察

1. 基本的なアプローチ（通常のナップサック問題との違い）

通常のナップサック問題であれば、DPテーブルの定義は dp[w] = (重さの合計が w のときの最大価値) のようになります。 しかし、本問題では「軽量化ケースをこれまでに何個使ったか」という情報も管理する必要があります。したがって、状態に「使用したケースの個数 \(k\)」を追加します。

• DPの状態定義: \(dp[k][w] = \)「これまでにケースを \(k\) 個使用し、持ち込む宝石の重さの合計が \(w\) であるときの最大価値」

2. 計算量とメモリの削減

素直に \(3\) 次元配列 dp[i][k][w]（\(i\) は \(i\) 番目までの宝石を考慮したことを表す）を定義すると、空間計算量は \(O(N K C)\) となります。 本問題の制約は \(N \le 10^5, C \le 10^5, K \le 30\) であるため、このままではメモリ制限を大幅に超過（MLE）してしまいます。

そこで、宝石 \(i\) のループを回しながらDPテーブルをインプレース（上書き）で更新していくことで、宝石のインデックス \(i\) の次元を削減し、空間計算量を \(O(K C)\) に抑えます。

---

アルゴリズム

1. テーブルの定義と初期化

サイズ \((K + 1) \times (C + 1)\) の配列 dp を用意します。 - 初期値はすべて \(-1\)（到達不可能）とします。 - 初期状態として、何も選んでいない状態 \(dp[0][0] = 0\) とします。

2. 配列の平坦化（高速化の工夫）

2次元配列 dp[K+1][C+1] をそのまま使う代わりに、1次元配列 dp[(K+1) * (C+1)] として平坦化して保持します。これにより、メモリの連続アクセス（キャッシュ効率）が向上し、実行時間が大幅に短縮されます。 インデックスの対応関係は以下の通りです。 $\(\text{dp}[k][w] \iff \text{dp}[k \times (C + 1) + w]\)$

3. DPの遷移

各宝石 \(i\)（価値 \(B_i\), 重さ \(W_i\), 半減後の重さ \(H_i = \lfloor W_i / 2 \rfloor\)）について、テーブルを更新します。

同じ宝石を重複して選ばないようにするため、\(k\) と \(w\) のループは必ず大きい方から（逆順に）回します。

\(dp[k][w]\) が有効な値（\(-1\) 以外）のとき、以下の \(2\) つの遷移を行います：

1. ケースを使わずに宝石 \(i\) を選ぶ \(w + W_i \le C\) のとき、 $\(dp[k][w + W_i] = \max(dp[k][w + W_i], dp[k][w] + B_i)\)$

2. ケースを使って宝石 \(i\) を選ぶ（\(k < K\) のとき） \(w + H_i \le C\) のとき、 $\(dp[k+1][w + H_i] = \max(dp[k+1][w + H_i], dp[k][w] + B_i)\)$

4. 枝刈り（さらなる高速化）

これまでに考慮した宝石の重さの合計の最大値 max_w を記録しておきます。 内側のループ（重量 \(w\) のループ）の開始点を \(\min(C, \text{max\_w})\) に制限することで、不必要な探索をスキップし、定数倍の高速化を図ることができます。

---

計算量

• 時間計算量: \(O(N \cdot K \cdot \min(C, \text{合計重量}))\) 最悪の場合でも \(O(NKC)\) です。問題の制約より \(N(K+1)(C+1) \le 2 \times 10^7\) であるため、実行時間制限に余裕で間に合います。さらに、枝刈りによって実際にはこれよりもはるかに高速に動作します。

• 空間計算量: \(O(K \cdot C)\) 保持するDPテーブルのサイズは \((K + 1) \times (C + 1)\) です。\(K \le 30, C \le 10^5\) より、要素数は最大で約 \(3.1 \times 10^6\) 個となり、long long 型（8バイト）を使用しても約 25 MB と非常に軽量です。

---

実装のポイント

• 逆順ループの重要性: インプレースでDPテーブルを更新する際、小さい \(w\) や \(k\) から順に更新してしまうと、同じ宝石を複数回使って遷移した結果（個数制限なしナップサック問題の挙動）になってしまいます。これを防ぐために、必ず \(k\) と \(w\) は降順でループを回す必要があります。

• オーバーフロー対策: 宝石の価値 \(B_i\) は最大で \(10^9\) であり、持ち込む宝石の価値の合計は \(10^{14}\) 程度に達することがあります。そのため、価値を格納するDPテーブルの型は 32bit 整数型（int）ではなく、64bit 整数型（long long）を使用する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, C, K;
    if (!(cin >> N >> C >> K)) return 0;

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

    // dp[k * (C + 1) + w]
    // k: 0..K, w: 0..C
    int stride = C + 1;
    vector<long long> dp((K + 1) * stride, -1);
    dp[0] = 0; // dp[0 * stride + 0] = 0

    int max_w = 0;

    for (int i = 0; i < N; ++i) {
        long long b = B[i];
        int w_val = W[i];
        int half_w = w_val / 2;

        int limit_w = min(C, max_w);

        for (int k = K; k >= 0; --k) {
            int k_stride = k * stride;
            int kp1_stride = (k + 1) * stride;

            for (int w = limit_w; w >= 0; --w) {
                long long val = dp[k_stride + w];
                if (val == -1) continue;

                // ケースなしで追加
                if (w + w_val <= C) {
                    long long& target = dp[k_stride + w + w_val];
                    if (val + b > target) {
                        target = val + b;
                    }
                }
                // ケースありで追加
                if (k + 1 <= K && w + half_w <= C) {
                    long long& target = dp[kp1_stride + w + half_w];
                    if (val + b > target) {
                        target = val + b;
                    }
                }
            }
        }
        max_w = min(C, max_w + w_val);
    }

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

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。