概要

この問題は、合計で \(D\) 日分以上の食事を賄うために必要な最小費用を求める問題です。各アイテム（食料パック）を何個でも選べることから、典型的な個数制限なしのナップサック問題（完全ナップサック問題）の最小化バージョンとして解くことができます。

考察

1. 問題の性質

各店で売られている食料パックは、何度でも購入することができます。目標は「合計日数を \(D\) 以上にする」ことですが、ちょうど \(D\) 日にする必要はなく、超えても構わないという点がポイントです。

2. 動的計画法（DP）の設計

「\(j\) 日分の食事を賄うための最小費用」を管理する配列 dp[j] を考えます。 通常のナップサック問題では「ちょうど \(j\)」を目指しますが、今回は「\(D\) 日以上」を求めたいので、以下のように定義します。

• dp[j] (\(0 \leq j < D\)): ちょうど \(j\) 日分の食事を賄うための最小費用
• dp[D]: \(D\) 日分以上の食事を賄うための最小費用

3. 最適化のポイント

• 不要なデータの削減: 同じ日数 \(F_i\) を賄えるパックが複数ある場合、最も価格 \(C_i\) が安いものだけを考慮すれば十分です。
• 日数の上限: \(D\) 日分あれば十分なので、1つのパックで賄える日数 \(F_i\) が \(D\) を超えている場合、それは \(F_i = D\) とみなして計算しても結果は変わりません。
• 遷移の工夫: \(j + F_i\) が \(D\) を超える場合は、すべて dp[D] の更新にまとめます。

アルゴリズム

個数制限なしのナップサック問題と同様に、1次元のDPテーブルを更新していきます。

1. 初期化:

   • dp[0] = 0
   • それ以外の dp[j] は非常に大きな値（無限大: INF）で初期化します。

2. 更新: 各店（または各日数ごとの最安値）のパック \((C_i, F_i)\) について、以下の遷移を行います。

   • \(j + F_i < D\) の場合: dp[j + F_i] = min(dp[j + F_i], dp[j] + C_i)
   • \(j + F_i \geq D\) の場合: dp[D] = min(dp[D], dp[j] + C_i)

   この更新を \(j = 0\) から順に行うことで、同じパックを複数回選ぶケースも自動的に考慮されます。

計算量

• 時間計算量: \(O(N + D^2)\)
  • 店の情報の整理に \(O(N)\)。
  • パックの種類数（最大 \(D\) 種類）に対して、DPテーブル（サイズ \(D\)）を走査するため、最悪 \(O(D^2)\) となります。
  • 制約が \(N, D \leq 3000\) なので、十分高速に動作します。
• 空間計算量: \(O(D)\)
  • 長さ \(D+1\) のDPテーブルを保持するためのメモリが必要です。

実装のポイント

• パックの重複排除: 同じ日数のパックが大量にある場合に備え、辞書や配列を使って日数ごとの最小コストをあらかじめまとめておくと、メインのDPループの回数を減らすことができます。

• 更新順序: 個数制限なしのナップサック問題では、同じアイテムを何度も選べるようにするため、インデックス \(j\) を小さい方から順にループさせて更新します。

• \(D\) 日を超える処理: j + f >= D となる場合の遷移を忘れずに dp[D] へ集約させることが、この問題を解く鍵となります。

  ソースコード

import sys

def solve():
    # Fast I/O to read all input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read N (number of shops) and D (number of days to cover)
    N = int(input_data[0])
    D = int(input_data[1])
    
    # Pre-process shops to keep only the cheapest price for each duration.
    # Any duration f > D is capped at D because we only need to cover at least D days.
    min_costs = {}
    idx = 2
    for _ in range(N):
        c = int(input_data[idx])
        f = int(input_data[idx+1])
        idx += 2
        
        if f > D:
            f = D
        
        if f not in min_costs or c < min_costs[f]:
            min_costs[f] = c
    
    # dp[j] stores the minimum cost to cover exactly j days for j < D.
    # dp[D] stores the minimum cost to cover at least D days.
    # Using a large integer for infinity.
    INF = 10**18
    dp = [INF] * (D + 1)
    dp[0] = 0
    
    # Convert min_costs to a list of (duration, cost) tuples
    shops = list(min_costs.items())
    
    for f, c in shops:
        # Standard unbounded knapsack optimization:
        # Update minimum cost for exactly j days where j < D.
        # The forward loop allows us to use the same shop multiple times.
        for j in range(D - f):
            if dp[j] < INF:
                new_v = dp[j] + c
                if new_v < dp[j + f]:
                    dp[j + f] = new_v
        
        # Update minimum cost for at least D days.
        # This state is reached by adding one more pack of duration f to any 
        # existing plan covering j days such that j + f >= D.
        # Since durations are capped at D, D - f will always be >= 0.
        for j in range(D - f, D):
            if dp[j] < INF:
                new_v = dp[j] + c
                if new_v < dp[D]:
                    dp[D] = new_v
                    
    # The answer is the minimum cost to cover at least D days.
    print(dp[D])

if __name__ == '__main__':
    solve()

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