概要

\(N\) 個の装備の中からいくつか選び、防御力の合計が \(K\) 以上になるようにして、攻撃力の合計を最大化する問題。

考察

この問題は典型的な「ナップサック問題」の変形です。通常のナップサック問題では「重みの和が〜以下」などの制約がありますが、今回は「防御力の和が \(K\) 以上」という下限が課されています。

素朴な全探索（\(2^N\) 通り）は \(N=100\) では計算量が爆発するので現実的ではありません（\(2^{100}\) は非常に大きい）。また、貪欲法も適用しづらく、例えば「攻撃力が高い順に選ぶ」などの戦略は、防御力の条件を満たさない可能性があるため、最適解にならないことがあります。

そこで、動的計画法（DP）を用いることを考えます。DPテーブルとして以下のように定義します：

\(dp[w] :=\) 防御力の合計がちょうど \(w\) となるような選び方の中で得られる最大攻撃力

ただし、防御力が \(K\) 以上であればよいので、\(w \geq K\) の部分はすべて \(w = K\) としてまとめてしまうことで、無駄を省けます。つまり、DPテーブルのサイズは最大でも \(K\) 程度で済みます。

更新は、各装備について「選ぶ」「選ばない」の分岐に対応します。ナップサック同様、後ろから更新することで、各アイテムを一度だけ使うという制約を自然に守れます。

最後に、\(dp[K]\) 以降の値のうち最大のものを答えとすればOKです。もしすべて -1（到達不能）なら、条件を満たす選び方は存在しないので -1 を出力します。

アルゴリズム

この問題は「部分和の種類によって評価値（攻撃力）を最大化するナップサック型DP」で解けます。

DPの定義：

• dp[w]: 防御力の合計がちょうど \(w\) となるように選んだときの、最大攻撃力（到達できない場合は -1）

ただし、\(w \geq K\) については、すべて \(w = K\) にマージして扱います（それ以上大きくしても意味がないため）。

更新方法：

各装備 \((W_i, S_i)\) に対して、\(w\) を大きい方から見て、

• dp[w] != -1 なら、
• 新しい状態 new_w = min(w + W_i, K) に対して、
• dp[new_w] = max(dp[new_w], dp[w] + S_i)

と更新します。これにより、各アイテムを1回だけ使う制約を満たしつつ、最大の攻撃力を求められます。

最終的な答え：

dp[K] 以降の値の最大値が答え。すべて -1 なら -1。

計算量

• 時間計算量: \(O(N \cdot K)\)
• 空間計算量: \(O(K)\)

\(N \leq 100\), \(K \leq 10^4\) なので十分高速です。

実装のポイント

• DPテーブルのサイズは min(sum(W), K)+1 で十分（防御力の上限を超える必要はない）
• 各アイテムを一度だけ使うために、内側のループは逆順に回す
• w >= K の場合はすべて K としてまとめる（インデックスを min(..., K) で抑える）
• 初期化は dp[0] = 0、それ以外は -1（未到達）

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    W = []
    S = []
    index = 2
    for _ in range(N):
        w = int(data[index])
        s = int(data[index+1])
        W.append(w)
        S.append(s)
        index += 2
    
    # dp[i][w] := i番目まで見て、防御力がちょうどwとなるときの最大攻撃力
    # ただし、w >= K についてはまとめて w = K として扱う
    max_w = min(sum(W), K)
    dp = [-1] * (max_w + 1)
    dp[0] = 0
    
    for i in range(N):
        w = W[i]
        s = S[i]
        # 逆順に更新することで、各アイテムを一度だけ使う制約を満たす
        for j in range(max_w, -1, -1):
            if dp[j] == -1:
                continue
            new_w = min(j + w, max_w)
            new_s = dp[j] + s
            if dp[new_w] < new_s:
                dp[new_w] = new_s
    
    result = -1
    for i in range(K, max_w + 1):
        if dp[i] > result:
            result = dp[i]
    
    print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。