概要

この問題は、高橋君がデパートの閉店時刻までに購入できる商品を選び、お得さの合計を最大化するナップサック問題の変種です。

考察

高橋君が購入可能な時間は \(T - S\) 分であり、各商品は購入手続きに \(C_i\) 分かかり、完了しないと購入できません。素朴に全探索すると \(2^N\) 通りの組み合わせを試すことになり、\(N \leq 100\) では計算量が大きすぎます。そこで、動的計画法を用いて効率的に解くことを考えます。

アルゴリズム

典型的なナップサック問題と同様に、動的計画法（DP）を使用します。DPテーブルを dp[j] = 時間 j 分まで使ったときの最大のお得さ と定義します。各商品について、残り時間が \(j\) 分のときにその商品を購入するかどうかを判断します。ただし、購入するためには \(j \geq C_i\) が必要です。

具体的には、各商品 \((C_i, P_i)\) について、利用可能な時間 \(j\) を \(T - S\) から \(C_i\) まで減少させながら、dp[j] = max(dp[j], dp[j - C_i] + P_i) で更新します。後ろから更新することで、同じ商品を複数回選ばないようにします。

計算量

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

実装のポイント

1. 利用可能な時間を available_time = T - S と計算します

2. DPテーブルは available_time + 1 のサイズで初期化します

3. 各商品について、時間のループを後ろから前に向かって処理します（同じ商品の重複選択を防ぐため）

4. available_time が0以下の場合（到着即閉店）は0を出力します

   ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    S = int(data[2])
    items = []
    index = 3
    for i in range(n):
        c = int(data[index])
        p = int(data[index+1])
        index += 2
        items.append((c, p))
    
    available_time = T - S
    dp = [0] * (available_time + 1)
    
    for c, p in items:
        for j in range(available_time, c - 1, -1):
            if dp[j] < dp[j - c] + p:
                dp[j] = dp[j - c] + p
                
    print(max(dp) if available_time > 0 else 0)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。