概要

制限時間 \(M\) 分以内で、いくつかの宿題を選んで完成度ポイントの合計を最大化する「0-1ナップサック問題」です。

考察

問題の本質

この問題は、各宿題を「選ぶ」か「選ばない」かの2択を繰り返し、時間制限内で得られるポイントを最大化する問題です。これは典型的な0-1ナップサック問題と呼ばれる有名な問題です。

素朴なアプローチとその問題点

最も単純な方法は、\(N\) 個の宿題それぞれについて「やる/やらない」の全パターンを試すことです。しかし、この場合 \(2^N\) 通りの組み合わせを調べる必要があり、\(N = 100\) のとき \(2^{100}\) は天文学的な数になるため、TLE（時間超過） になります。

解決策：動的計画法（DP）

重複する計算を避けるために、動的計画法を使います。

「時間 \(j\) を使ったときに得られる最大ポイント」を記録しながら、宿題を1つずつ処理していきます。

アルゴリズム

DPの定義

\(dp[j]\) = ちょうど \(j\) 分以下の時間を使ったときの完成度ポイントの最大値

遷移の考え方

各宿題 \((R_i, T_i)\) について、時間 \(j\) を使う場合を考えます： - その宿題を選ばない場合: \(dp[j]\) はそのまま - その宿題を選ぶ場合: \(dp[j-T_i] + R_i\)（\(T_i\) 分前の状態にポイント \(R_i\) を加える）

この2つの大きい方を新しい \(dp[j]\) とします。

具体例

\(N=3, M=5\) で、宿題が \((R_1, T_1) = (4, 2), (R_2, T_2) = (5, 3), (R_3, T_3) = (3, 2)\) の場合：

1. 初期状態: \(dp = [0, 0, 0, 0, 0, 0]\)（時間0〜5）
2. 宿題1 \((4, 2)\) 処理後: \(dp = [0, 0, 4, 4, 4, 4]\)
3. 宿題2 \((5, 3)\) 処理後: \(dp = [0, 0, 4, 5, 5, 9]\)
4. 宿題3 \((3, 2)\) 処理後: \(dp = [0, 0, 4, 5, 7, 9]\)

答えは \(\max(dp) = 9\)（宿題1と宿題2を選ぶ）

なぜ逆順に更新するのか？

順方向（\(j = 0\) から \(M\) へ）に更新すると、同じ宿題を何度も使ってしまう可能性があります。

例えば、宿題 \((R=4, T=2)\) を処理するとき： - \(dp[2] = dp[0] + 4 = 4\)（1回使用） - \(dp[4] = dp[2] + 4 = 8\)（2回使用してしまう！）

逆順（\(j = M\) から \(T\) へ）に更新すれば、まだ更新されていない古い \(dp\) 値を参照するため、各宿題を1回だけ使うことが保証されます。

計算量

• 時間計算量: \(O(N \times M)\)
  • \(N\) 個の宿題それぞれについて、\(M\) 回のループを行う
  • \(N = 100, M = 10^5\) で最大 \(10^7\) 回程度の演算
• 空間計算量: \(O(M)\)
  • 1次元配列 \(dp\) のサイズ

実装のポイント

• 1次元DPで空間を節約: 2次元配列 \(dp[i][j]\)（\(i\) 番目までの宿題で時間 \(j\)）を使う方法もありますが、1次元配列で逆順更新することでメモリを削減できます

• ループの範囲: range(M, T - 1, -1) で \(j = M\) から \(j = T\) まで逆順に回す（\(j < T\) のときは宿題を選べないのでスキップ）

• 最終的な答え: max(dp) で時間 \(M\) 以下で達成可能な最大ポイントを得る（dp[M] と同じ値になる）

  ソースコード

def solve():
    N, M = map(int, input().split())
    items = []
    for _ in range(N):
        R, T = map(int, input().split())
        items.append((R, T))
    
    # 0-1ナップサック問題
    # dp[j] = 時間jを使ったときの完成度ポイントの最大値
    dp = [0] * (M + 1)
    
    for R, T in items:
        # 逆順に更新することで、各アイテムを1回だけ使用する
        for j in range(M, T - 1, -1):
            dp[j] = max(dp[j], dp[j - T] + R)
    
    print(max(dp))

solve()

---

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