概要

この問題は、制限時間 \(M\) 分の中である宿題の部分集合を選び、得られる完成度ポイントの合計を最大化するナップサック問題の応用です。

考察

この問題は典型的な「0-1 ナップサック問題」として知られています。
各宿題は「重み（必要時間 \(T_i\)）」と「価値（完成度ポイント \(R_i\)）」を持っており、制限時間 \(M\) 以内で価値の合計を最大化することが目的です。

素朴な全探索（すべての部分集合を考える）では、宿題の数 \(N\) が最大100なので、\(2^{100}\) 通りとなり、到底計算できません（TLE）。
また、貪欲法（例えば「ポイント/時間」の比率が高い順に取る）も、この問題では最適解を保証しないため、WAになります。

そこで、動的計画法（DP）を用いるのが有効です。
DPテーブル dp[t] を「時間 \(t\) 以内で得られる最大の完成度ポイント」と定義します。
各宿題について、時間を大きい方から更新していくことで、同じ宿題を複数回選んでしまうことを防ぎます。

アルゴリズム

動的計画法（DP）を用います。

DPの定義

• dp[t]: 時間 \(t\) 以内で得られる最大の完成度ポイント

更新方法

各宿題 \(i\)（完成度 \(r = R_i\), 必要時間 \(t = T_i\)）に対して： - 時間 \(j\) を \(M\) から \(t\) まで逆順に走査し、以下のように更新：

  if dp[j] < dp[j - t] + r:
      dp[j] = dp[j - t] + r

• 逆順にすることで、同じ宿題を複数回選ぶのを防ぐ（1回しか使われない）

最終的な答え

• max(dp) が求める最大値

計算量

• 時間計算量: \(O(N \times M)\)
• 空間計算量: \(O(M)\)

実装のポイント

• DPテーブルの更新は必ず逆順に行うこと。これにより、1つのアイテム（宿題）を複数回選択してしまうバグを回避できます。
• dp[0] = 0 として初期化し、それ以外の dp[t] は0で初期化しておきます。
• 最後に max(dp) を出力することで、時間 \(M\) 以内での最大ポイントを得られます。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    R = []
    T = []
    
    for i in range(N):
        R.append(int(data[2 + 2 * i]))
        T.append(int(data[3 + 2 * i]))
    
    # DPテーブル: dp[t] = 時間t以内で得られる最大の完成度ポイント
    dp = [0] * (M + 1)
    
    for i in range(N):
        r = R[i]
        t = T[i]
        # 逆順に更新しないと、同じアイテムを複数回使ってしまう可能性がある
        for j in range(M, t - 1, -1):
            if dp[j] < dp[j - t] + r:
                dp[j] = dp[j - t] + r
    
    print(max(dp))

if __name__ == "__main__":
    main()

---

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