概要

この問題は、限られた時間の中で得られる「お得さ」の合計を最大化する問題です。 実質的には、利用可能な時間を「ナップサックの容量」、商品の購入時間を「重さ」、お得さを「価値」と見なすことで、典型的な 「0/1ナップサック問題」 として解くことができます。

考察

まず、高橋君が買い物に使える合計時間を整理します。 セールは時刻 \(T\) に終了し、高橋君は時刻 \(S\) に到着するため、買い物に使える時間は \(T - S\) 分間です。

次に、この問題を解くためのポイントを考えます。 - 各商品は「買う」か「買わない」かの2択です（同じ商品を複数回買うことはできません）。 - 商品の購入手続きは途中でやめることができず、閉店時刻 \(T\) を過ぎてはいけません。 - 商品の数 \(N\) は最大 100、残り時間は最大 \(10^4\) です。

もし、すべての商品の組み合わせを試そうとすると \(2^N = 2^{100}\) 通りとなり、制限時間内に計算が終わりません。しかし、今回の制約（\(N \leq 100\) かつ 合計時間 \(\leq 10^4\)）であれば、動的計画法 (DP) を用いることで効率的に正解を求めることができます。

アルゴリズム

動的計画法（0/1ナップサック問題）

以下の DP テーブルを定義します。 - dp[j]：合計時間が \(j\) 分以内であるときに得られる「お得さ」の最大合計値

このテーブルを、各商品 \(i = 1, \dots, N\) について順番に更新していきます。 商品 \(i\)（時間 \(C_i\)、お得さ \(P_i\)）を検討するとき、更新式は以下のようになります。

\[dp[j] = \max(dp[j], dp[j - C_i] + P_i)\]

これは、「商品 \(i\) を買わない場合（現在の値）」と「商品 \(i\) を買う場合（\(C_i\) 分前の最大値にお得さを足したもの）」を比較して、大きい方を採用するという意味です。

更新の注意点

1次元の配列で DP を行う場合、内側のループ（時間の更新）は 後ろ（残り時間 \(T-S\)）から逆順に 行う必要があります。 前から更新してしまうと、同じ商品を何度も選んでしまう（個数制限のないナップサック問題になる）ためです。

計算量

• 時間計算量: \(O(N \times (T - S))\)
  • 商品の数 \(N\) と残り時間に比例します。最大で \(100 \times 10^4 = 10^6\) 回程度の計算となり、実行時間制限内に十分収まります。
• 空間計算量: \(O(T - S)\)
  • 残り時間分の長さを持つ DP テーブルを保持するためです。最大で \(10^4\) 程度の要素数になります。

実装のポイント

• 残り時間の算出: まず \(T - S\) を計算し、これをナップサックの容量として扱います。

• 逆順ループ: Python では range(available_time, c - 1, -1) のように書くことで、後ろから安全に DP テーブルを更新できます。

• 入力の受け取り: \(N\) や \(T\) などの値が大きく、商品数も多いため、sys.stdin.read().split() などを使って一括で読み込むと処理が高速になります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行など）で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # データを数値に変換するためのイテレータを作成します
    it = map(int, input_data)
    
    # 商品数 N、閉店時刻 T、到着時刻 S を取得します
    try:
        n = next(it)
        t = next(it)
        s = next(it)
    except StopIteration:
        return
        
    # 高橋君が買い物に使える残り時間を計算します
    # 閉店時刻 T までに手続きが完了する必要があるため、利用可能な時間は T - S です
    available_time = t - s
    
    # 動的計画法（DP）のためのテーブルを初期化します
    # dp[w] は、合計時間が w 分以内の時に得られる最大のお得さを表します
    # 制約より available_time は最大で 10^4 です
    dp = [0] * (available_time + 1)
    
    # 各商品について処理を行います
    for _ in range(n):
        try:
            c = next(it)  # 購入手続きにかかる時間
            p = next(it)  # 得られるお得さ
        except StopIteration:
            break
            
        # 商品の手続き時間が残り時間より長い場合は購入できません
        if c > available_time:
            continue
        
        # 0/1 ナップサック問題の標準的な更新処理です
        # 同じ商品を複数回選ばないよう、時間を後ろから逆順にループします
        for j in range(available_time, c - 1, -1):
            # 現在の商品を購入する場合のお得さを計算し、既存の最大値と比較して更新します
            new_profit = dp[j - c] + p
            if new_profit > dp[j]:
                dp[j] = new_profit
                
    # 利用可能な時間内での最大のお得さを出力します
    print(dp[available_time])

if __name__ == '__main__':
    solve()

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