概要

\(N\) 個の装備品から1個以上を選び、防御力の合計が \(K\) 以上という条件のもとで、攻撃力の合計を最大化する問題です。これは条件付きの0-1ナップサック問題として解くことができます。

考察

素朴なアプローチ（全探索）

\(N\) 個の装備それぞれに「選ぶ／選ばない」の2通りがあるため、全探索では \(2^N\) 通りを調べる必要があります。\(N \leq 100\) のとき \(2^{100}\) は天文学的な数であり、到底間に合いません。

重要な気づき

この問題は0-1ナップサック問題の変形です。通常のナップサック問題は「重さの合計が上限 \(K\) 以下」という制約ですが、本問では「防御力の合計が \(K\) 以上」という制約になっています。

ここで鍵となるのが、防御力の合計が \(K\) を超えた分は区別する必要がないという点です。防御力が \(K\) であろうと \(K+100\) であろうと、条件「\(K\) 以上」は同様に満たされます。したがって、DPの状態として防御力を \(0\) から \(K\) までの範囲に収め、\(K\) 以上はすべて \(K\) にまとめることができます。

アルゴリズム

0-1ナップサックDP を用います。

• 状態: \(dp[w]\) = 防御力の合計がちょうど \(w\) となるような装備の選び方における、攻撃力の合計の最大値（ただし \(w = K\) は「防御力が \(K\) 以上」を表す）
• 初期状態: \(dp[0] = 0\)、それ以外は \(-1\)（達成不可能）
• 遷移: 各装備 \((W_i, S_i)\) について、現在の \(dp[w]\) が有効な全ての \(w\) に対して、新しい防御力 \(\min(w + W_i, K)\) への遷移を考える： $\(dp'[\min(w + W_i, K)] = \max(dp'[\min(w + W_i, K)],\ dp[w] + S_i)\)$

\(\min(w + W_i, K)\) とすることで、\(K\) 以上の防御力をすべて添字 \(K\) に集約しています。

• 各装備を高々1回しか使えないため、遷移時に元の \(dp\) のコピー（new_dp = dp[:]）を用いて更新します。

最終的に \(dp[K]\) が \(-1\) でなければそれが答え、\(-1\) なら条件を満たす選び方が存在しません。

具体例

\(N=3, K=5\) で装備が \((W, S) = (3, 10), (2, 8), (4, 15)\) の場合： - 装備1と装備2を選ぶと防御力 \(3+2=5 \geq 5\)、攻撃力 \(10+8=18\) - 装備1と装備3を選ぶと防御力 \(3+4=7 \geq 5\)、攻撃力 \(10+15=25\) - 装備2と装備3を選ぶと防御力 \(2+4=6 \geq 5\)、攻撃力 \(8+15=23\)

よって答えは \(25\) です。

計算量

• 時間計算量: \(O(N \times K)\)
  • 装備 \(N\) 個それぞれについて、\(0\) から \(K\) までの状態を走査するため
• 空間計算量: \(O(K)\)
  • DPテーブルのサイズ

\(N \leq 100\)、\(K \leq 10^4\) なので、最大でも \(100 \times 10^4 = 10^6\) 回程度の演算で十分高速です。

実装のポイント

• 防御力の上限丸め込み: nw = min(w + W, K) により、\(K\) 以上の防御力をすべて添字 \(K\) に集約する。これがこの問題の最大のポイントです。

• 0-1ナップサックの更新方法: 各装備を1回だけ使うために、new_dp = dp[:] とコピーを作ってから更新しています。通常の0-1ナップサックでは逆順ループで対処しますが、本問では遷移先が min(w+W, K) と複数の \(w\) から同じ添字に集まるため、コピーを使う方が安全です。

• 到達不可能状態の管理: \(-1\) を「未到達」として扱い、遷移元が \(-1\) の場合はスキップします。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        W = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        items.append((W, S))
    
    # dp[w] = maximum attack power achievable with exactly defense w
    # We cap w at K since any defense >= K is equivalent for our purposes
    # dp[w] for w = 0..K, where dp[K] represents "defense >= K"
    
    NEG_INF = -1
    dp = [NEG_INF] * (K + 1)
    dp[0] = 0
    
    for W, S in items:
        # Traverse in reverse to ensure each item is used at most once
        new_dp = dp[:]
        for w in range(K + 1):
            if dp[w] == NEG_INF:
                continue
            nw = min(w + W, K)
            if new_dp[nw] < dp[w] + S:
                new_dp[nw] = dp[w] + S
        dp = new_dp
    
    if dp[K] == NEG_INF:
        print(-1)
    else:
        print(dp[K])

solve()

---

この解説は claude4.6opus-thinking によって生成されました。