概要

この問題は、限られた制限時間 \(M\) の中で、複数の候補（宿題）からどれを選ぶと得られる価値（完成度ポイント）の合計を最大化できるかという、典型的な「0/1ナップサック問題」です。

考察

1. 全探索は可能か？

各宿題について「やる」か「やらない」かの2択があるため、すべての組み合わせを調べると \(2^N\) 通りのパターンが存在します。今回の制約では \(N=100\) であるため、組み合わせの数は \(2^{100} \approx 1.26 \times 10^{30}\) となり、制限時間内に計算が終わることはありません。

2. 貪欲法は可能か？

「1分あたりのポイントが高い順に選ぶ」という貪欲法も考えられますが、この方法では最適解を得られません。例えば、残り時間が10分で、「ポイント10・時間10」の宿題と、「ポイント6・時間5」の宿題が2つある場合を考えます。 - 効率で見ると、前者は \(10/10 = 1\)、後者は \(6/5 = 1.2\) です。 - 効率の良い後者から選ぶと「6ポイント×1つ」しか選べず、残りは5分なので前者は選べません。 - しかし、後者を2つ選べば \(6+6=12\) ポイントとなり、こちらの方が高いスコアになります。

このように、アイテムを分割できない（0か1か）という条件では、単純な効率順では解けないため、動的計画法 (DP) を用います。

アルゴリズム

動的計画法 (DP) による解決

「\(i\) 番目までの宿題を使って、合計時間が \(j\) 分のときに得られる最大ポイント」を記録しながら計算を進めます。

今回はメモリを節約するため、1次元配列を用いたDPで解いています。 - 配列の定義: dp[j] = 合計時間が \(j\) 分以下であるときに得られる完成度ポイントの最大値 - 初期状態: dp[0...M] = 0

更新式

新しい宿題（ポイント \(R_i\), 時間 \(T_i\)）を検討する際、各時間 \(j\) について以下のように更新します。 $\(dp[j] = \max(dp[j], dp[j - T_i] + R_i)\)\( これは、「今の宿題をやらない場合（これまでの最大値）」と「今の宿題をやる場合（残り時間 \)j - T_i$ での最大値 ＋ 今回のポイント）」を比較して、大きい方を採用するという意味です。

計算量

• 時間計算量: \(O(N \times M)\)
  • 宿題の数 \(N\) 回のループの中で、時間 \(M\) 分のループを回すためです。
  • 今回の制約では \(100 \times 10^5 = 10^7\) となり、Pythonでも十分に制限時間内に間に合います。
• 空間計算量: \(O(M)\)
  • 時間 \(M\) 分に対応する1次元配列を保持するためです。

実装のポイント

• 逆順でのループ: 1次元配列でDPを更新する場合、内側のループ（時間のループ）は \(M\) から \(T_i\) に向かって逆順に回す必要があります。正順で更新してしまうと、同じ宿題を「1回使った後の値」を元にさらに同じ宿題を足してしまう（重複使用）可能性があるためです。

• 大きな値への対応: 完成度ポイント \(R_i\) は最大 \(10^9\) であり、合計は非常に大きな値になります。Pythonは標準で多倍長整数を扱えるため、オーバーフローを気にせずそのまま計算できます。”`markdown

  概要

  この問題は、限られた制限時間 \(M\) の中で、複数の候補（宿題）からどれを選ぶと得られる価値（完成度ポイント）の合計を最大化できるかという、典型的な「0/1ナップサック問題」です。

考察

1. 全探索は可能か？

各宿題について「やる」か「やらない」かの2択があるため、すべての組み合わせを調べると \(2^N\) 通りのパターンが存在します。今回の制約では \(N=100\) であるため、組み合わせの数は \(2^{100} \approx 1.26 \times 10^{30}\) となり、制限時間内に計算が終わることはありません。

2. 貪欲法は可能か？

「1分あたりのポイントが高い順に選ぶ」という貪欲法も考えられますが、この方法では最適解を得られません。例えば、残り時間が10分で、「ポイント10・時間10」の宿題と、「ポイント6・時間5」の宿題が2つある場合を考えます。 - 効率で見ると、前者は \(10/10 = 1\)、後者は \(6/5 = 1.2\) です。 - 効率の良い後者から選ぶと「6ポイント×1つ」しか選べず、残りは5分なので前者は選べません。 - しかし、後者を2つ選べば \(6+6=12\) ポイントとなり、こちらの方が高いスコアになります。

このように、アイテムを分割できない（0か1か）という条件では、単純な効率順では解けないため、動的計画法 (DP) を用います。

アルゴリズム

動的計画法 (DP) による解決

「\(i\) 番目までの宿題を使って、合計時間が \(j\) 分のときに得られる最大ポイント」を記録しながら計算を進めます。

今回はメモリを節約するため、1次元配列を用いたDPで解いています。 - 配列の定義: dp[j] = 合計時間が \(j\) 分以下であるときに得られる完成度ポイントの最大値 - 初期状態: dp[0...M] = 0

更新式

新しい宿題（ポイント \(R_i\), 時間 \(T_i\)）を検討する際、各時間 \(j\) について以下のように更新します。 $\(dp[j] = \max(dp[j], dp[j - T_i] + R_i)\)\( これは、「今の宿題をやらない場合（これまでの最大値）」と「今の宿題をやる場合（残り時間 \)j - T_i$ での最大値 ＋ 今回のポイント）」を比較して、大きい方を採用するという意味です。

計算量

• 時間計算量: \(O(N \times M)\)
  • 宿題の数 \(N\) 回のループの中で、時間 \(M\) 分のループを回すためです。
  • 今回の制約では \(100 \times 10^5 = 10^7\) となり、Pythonでも十分に制限時間内に間に合います。
• 空間計算量: \(O(M)\)
  • 時間 \(M\) 分に対応する1次元配列を保持するためです。

実装のポイント

• 逆順でのループ: 1次元配列でDPを更新する場合、内側のループ（時間のループ）は \(M\) から \(T_i\) に向かって逆順に回す必要があります。正順で更新してしまうと、同じ宿題を「1回使った後の値」を元にさらに同じ宿題を足してしまう（重複使用）可能性があるためです。
• 大きな値への対応: 完成度ポイント \(R_i\) は最大 \(10^9\) であり、合計は非常に大きな値になります。Pythonは標準で多倍長整数を扱えるため、オーバーフローを気にせずそのまま計算できます。

## ソースコード

```python
import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 宿題の数 N と残り時間 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # dp[j] は、合計時間が j 分以下であるときに得られる完成度ポイントの最大値を表します
    # 初期値はすべて0（どの宿題も選んでいない状態）
    dp = [0] * (M + 1)
    
    # 各宿題について情報を取得し、DPテーブルを更新します
    for i in range(N):
        # 宿題 i の完成度ポイント r と必要時間 t
        r = int(input_data[2 + 2*i])
        t = int(input_data[3 + 2*i])
        
        # 0/1ナップサック問題の標準的な更新方法です
        # 各宿題を1回だけ選べるようにするため、後ろから（Mからtまで）更新します
        for j in range(M, t - 1, -1):
            # 宿題 i を選んだ場合のポイント
            new_val = dp[j - t] + r
            # 既存のポイントより大きければ更新
            if new_val > dp[j]:
                dp[j] = new_val
                
    # dp[M] には残り時間 M 分以内での最大完成度ポイントが格納されています
    print(dp[M])

if __name__ == '__main__':
    solve()

---

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