概要

高橋君が限られた時間内で商品を選び、お得さの合計を最大化する問題です。

考察

この問題は典型的な「制限時間内にお得さ（価値）の合計を最大化する」ナップサック問題の変形です。
ここでいう「重み」は商品の購入にかかる時間 \(C_i\) 、「価値」はお得さ \(P_i\) に対応します。

• 高橋君が買い物に使える時間は \(T - S\) 分です。これを「容量」だと見なします。
• 各商品は1つしか選べません（同じ商品を2回買えない）。
• 商品の購入順序は関係なく、選んだ商品群の合計時間が \(T - S\) 以下であれば良いです。

素朴な全探索では？

全ての商品の組み合わせを試すと、\(2^N\) 通りとなり、\(N=100\) のときに現実的ではありません（TLE）。

どう解決するか？

動的計画法（DP）を使います。
DPテーブル dp[t] を「時間 \(t\) 以内で得られる最大のお得さ」として管理します。
各商品について、時間を後ろから更新することで、1つの商品を複数回使ってしまうことを防ぎます。

たとえば： - 時間3分以内で、商品A（時間2分、お得さ3）と商品B（時間1分、お得さ2）を使う場合、
　→ Aを買ってからBを買うことで、合計3分でお得さ5が得られます。

アルゴリズム

これは 0-1 ナップサック問題 そのものです。

ステップ

1. 使用可能時間を available_time = T - S とする。
2. DPテーブル dp[0..available_time] を初期化（全部0）。
3. 各商品 \((C_i, P_i)\) に対して、時間 \(t\) を available_time から \(C_i\) まで後ろからループさせ：
   • dp[t] = max(dp[t], dp[t - C_i] + P_i) を更新
4. 最終的に max(dp) が答え。

なぜ後ろから？

同じ商品を複数回使わないようにするためです。前から更新すると、同じ商品が何度も使われてしまう可能性があります。

計算量

• 時間計算量: \(O(N \cdot (T - S))\)
• 空間計算量: \(O(T - S)\)

実装のポイント

• 時間の上限が最大 \(10^4\) なので、DPによる解法が有効。
• 各商品の処理時にDP配列を後ろから更新すること。
• 入力を高速に読み込むとより安全（特にPythonでは sys.stdin.read など）。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    T = int(data[1])
    S = int(data[2])
    
    items = []
    index = 3
    for _ in range(N):
        C = int(data[index])
        P = int(data[index+1])
        items.append((C, P))
        index += 2
    
    # 使用可能な時間
    available_time = T - S
    
    # DPテーブル: dp[t] = 時間 t 以内で得られる最大お得さ
    dp = [0] * (available_time + 1)
    
    for C, P in items:
        # 後ろから更新することで各アイテムを一度だけ使うようにする
        for t in range(available_time, C - 1, -1):
            if dp[t] < dp[t - C] + P:
                dp[t] = dp[t - C] + P
    
    print(max(dp))

if __name__ == "__main__":
    main()

---

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