概要

防御力の合計が \(K\) 以上になるように装備を選び、その中で攻撃力合計を最大化する問題です。各装備は高々1回しか選べないため、典型的な「0/1 ナップサックDP」で解けます。

考察

• 条件は「防御力合計が ちょうど \(K\)」ではなく「\(K\) 以上」です。
  しかし、\(K\) を超えた分はそれ以上細かく区別しなくても、最終的に必要なのは「条件達成できるか」と「最大攻撃力」だけです。
• 素朴に「全ての部分集合を試す」と \(2^N\) 通りになり、\(N \le 100\) では到底間に合いません。
• そこで、「防御力の合計」を状態にして、そこまで到達したときの「最大攻撃力」をDPで管理します。
• ただし防御力は最大で \(10^4\)、合計はもっと大きくなり得ますが、\(K\) を超えたら全部まとめて \(K\) として扱う（打ち切り）ことで、状態数を \(K+1\) 個に抑えられます。

例：\(K=10\) のとき、防御力合計が \(10,11,100\) の違いは「入場条件を満たす」という点で同じなので、すべて状態 \(10\) にまとめます。

アルゴリズム

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

• \(dp[w]\)：防御力合計を \(w\)（ただし \(w\) は \(0 \sim K\)、\(K\) は「\(K\) 以上」を代表）にできるときの、攻撃力合計の最大値
  
• 到達不可能な状態は非常に小さい値（\(-\infty\)）で表す

初期化： - \(dp[0]=0\)（何も選ばない） - それ以外は \(-\infty\)

各装備 \((W_i, S_i)\) について、0/1（1回まで）なので 後ろから更新します： - 現在の状態 \(w\) から装備を追加すると、新しい防御力は \(nw = \min(K, w + W_i)\) - 攻撃力は \(dp[w] + S_i\) - より大きい攻撃力が得られるなら更新する

最終的に - \(dp[K]\) が \(-\infty\) なら条件を満たす選び方が存在しないので -1 - そうでなければ \(dp[K]\) が答え

計算量

• 時間計算量: \(O(NK)\)
  （各装備ごとに \(w=0\sim K\) を更新）
• 空間計算量: \(O(K)\)
  （DP配列1本のみ）

実装のポイント

• 後ろからループ（for w in range(K, -1, -1)）することで、同じ装備を1回の処理中に複数回使ってしまうのを防ぎます（0/1ナップサックの基本）。

• \(w+W_i\) が \(K\) を超えたら K に丸める（打ち切り）ことで、「\(K\) 以上」を正しく扱えます。

• 到達不可能判定のために NEG = -10**18 のような十分小さい値を使い、dp[w] == NEG の状態は遷移しないようにします。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    NEG = -10**18
    dp = [NEG] * (K + 1)
    dp[0] = 0

    for w_i, s_i in items:
        for w in range(K, -1, -1):
            if dp[w] == NEG:
                continue
            nw = w + w_i
            if nw > K:
                nw = K
            val = dp[w] + s_i
            if val > dp[nw]:
                dp[nw] = val

    print(dp[K] if dp[K] != NEG else -1)

if __name__ == "__main__":
    main()

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