概要

この問題は、有名な「0-1ナップサック問題」に「重さを半分にする軽量化ケースを最大 \(K\) 個使える」という条件が加わった応用問題です。動的計画法（DP）を用いて、ケースの使用回数と現在の総重量を状態として管理することで、制限時間内に最適解を求めることができます。

考察

1. 基本的な考え方（0-1 ナップサック問題との類似性）

もし軽量化ケースが存在しない（\(K = 0\)）場合、この問題は標準的な「0-1ナップサック問題」そのものです。 標準的なナップサック問題では、以下のようなDPテーブルを定義します。 - dp[w] = 総重量が w のときの価値の最大値

今回は「軽量化ケースを何個使ったか」という情報も管理する必要があるため、DPの状態に「ケースの使用回数」を追加します。

2. 状態の定義

DPテーブルを以下のように定義します。 - \(dp[j][w]\) ： これまでに見た宝石の中からいくつか選び、軽量化ケースを \(j\) 回使い、総重量が \(w\) であるときの価値の最大値

ここで、ケースの使用回数 \(j\) は \(0 \leq j \leq K\)、総重量 \(w\) は \(0 \leq w \leq C\) の範囲を動きます。

3. 遷移の考え方

各宝石 \(i\) （元の重さ \(W_i\)、価値 \(B_i\)、半分にした重さ \(W_{\text{half}} = \lfloor W_i / 2 \rfloor\)）について、選ぶか選ばないかの遷移を考えます。 宝石 \(i\) を選ぶ場合、以下の2つの選択肢があります。

1. 軽量化ケースを使わずに選ぶ（\(W_i \leq C\) の場合のみ可能）

   • ケースの使用回数 \(j\) は変化しません。
   • \(dp[j][w] \leftarrow dp[j][w - W_i] + B_i\)

2. 軽量化ケースを使って選ぶ（\(j \geq 1\) かつ \(W_{\text{half}} \leq C\) の場合のみ可能）

   • ケースの使用回数が \(j-1\) から \(j\) に増えます。
   • \(dp[j][w] \leftarrow dp[j-1][w - W_{\text{half}}] + B_i\)

これらを踏まえて、DPテーブルを後ろから（\(w\) や \(j\) を大きい方から）更新していくことで、同じ宝石を複数回選んでしまう重複を防ぎながら、1次元（\(j\) と \(w\) の2次元）の配列でメモリを節約しつつ更新できます。

4. 高速化の工夫（定数倍高速化）

制約より \(N(K+1)(C+1) \leq 2 \times 10^7\) であり、単純な3重ループ（宝石 \(N\) \(\times\) ケース数 \(K\) \(\times\) 容量 \(C\)）では、Pythonなどの実行速度が比較的遅い言語において実行時間制限（TLE）になる可能性があります。 そのため、以下の高速化を行います。

• 到達可能範囲の制限: これまでに選んだ宝石の最大の重さの合計 max_w を記録しておき、DPの遷移で探索する重さ \(w\) の上限を \(\min(C, \text{max\_w} + W_i)\) に制限します。これにより、序盤のループ回数を大幅に削減できます。
• 不要な宝石のスキップ: 半分にしても重さが \(C\) を超える宝石（\(W_{\text{half}} > C\)）は、絶対に持ち込めないため最初から無視します。

---

アルゴリズム

1. 初期化:

   • \(dp[j][w]\) をすべて \(-1\)（到達不可能）で初期化します。ただし、\(dp[0][0] = 0\) とします。
   • これまでに到達可能な最大重量を表す変数 max_w = 0 を用意します。

2. DPの遷移: 各宝石 \((W, B)\) について以下を行います。

   • \(W_{\text{half}} = \lfloor W / 2 \rfloor\) を計算します。\(W_{\text{half}} > C\) ならスキップします。
   • ループの上限 limit_w を、ケースを使う場合と使わない場合に応じて適切に設定します。
   • ケースの使用回数 \(j\) を \(K\) から \(0\) まで逆順にループします。
     • \(j > 0\) のとき、ケースを使用する遷移（\(dp[j-1]\) からの遷移）と、ケースを使用しない遷移（\(dp[j]\) からの遷移）の両方を考慮して \(dp[j][w]\) を更新します。
     • \(j = 0\) のとき、ケースを使用しない遷移のみを考慮して \(dp[0][w]\) を更新します。
   • max_w を更新します。

3. 答えの出力:

   • DPテーブル全体の最大値（すべての \(j, w\) における \(dp[j][w]\) の最大値）が答えとなります。

---

計算量

時間計算量: \(O(NKC)\)

最悪の場合でもループの回数は \(N \times (K+1) \times (C+1)\) に比例します。制約より \(N(K+1)(C+1) \leq 2 \times 10^7\) であるため、定数倍高速化を施した実装により、制限時間内に余裕で間に合わせることができます。

空間計算量: \(O(KC)\)

DPテーブルに必要なメモリは \((K+1) \times (C+1)\) のサイズです。\(K \le 30\)、\(C \le 10^5\) であるため、要素数は最大でも約 \(3.1 \times 10^6\) 個となり、メモリ制限に対しても非常に安全です。

---

実装のポイント

• 逆順でのループ: 同じ宝石を2回以上選ぶ「個数制限なしナップサック問題」になってしまわないよう、重さ \(w\) およびケース数 \(j\) のループは必ず大きい方から（逆順に）回す必要があります。

• 遷移の条件分岐: 宝石の元の重さ \(W\) が \(C\) を超えている場合、ケースを使わずにその宝石を選ぶことはできません。コード内では W <= C かどうかで条件分岐を行い、無効な遷移（配列の範囲外参照や不適切な状態更新）を防いでいます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    C = int(data[1])
    K = int(data[2])
    
    items = []
    idx = 3
    for _ in range(N):
        B = int(data[idx])
        W = int(data[idx+1])
        items.append((W, B))
        idx += 2
        
    dp = [[-1] * (C + 1) for _ in range(K + 1)]
    dp[0][0] = 0
    
    max_w = 0
    for W, B in items:
        W_half = W // 2
        if W_half > C:
            continue
        
        if W <= C:
            limit_w = min(C, max_w + W)
        else:
            limit_w = min(C, max_w + W_half)
            
        for j in range(K, -1, -1):
            dp_j = dp[j]
            if j > 0:
                dp_j_prev = dp[j-1]
                if W <= C:
                    for w in range(limit_w, W - 1, -1):
                        v1 = dp_j[w - W]
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v1 != -1:
                            t = v1 + B
                            if t > mx: mx = t
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                    
                    start_w = min(limit_w, W - 1)
                    for w in range(start_w, W_half - 1, -1):
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                else:
                    for w in range(limit_w, W_half - 1, -1):
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
            else:
                if W <= C:
                    for w in range(limit_w, W - 1, -1):
                        v1 = dp_j[w - W]
                        mx = dp_j[w]
                        if v1 != -1:
                            t = v1 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                        
        if W <= C:
            max_w = min(C, max_w + W)
        else:
            max_w = min(C, max_w + W_half)
            
    ans = 0
    for j in range(K + 1):
        for w in range(C + 1):
            if dp[j][w] > ans:
                ans = dp[j][w]
    print(ans)

if __name__ == '__main__':
    solve()

---

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