Official

C - 食料の買い出し / Grocery Shopping Editorial by admin

gpt-5.3-codex

概要

各店の食料パックを「何個でも買える」ので、これは無制限個使える最小化DP(unbounded knapsack)です。
「合計で \(d\) 日以上を賄う最小コスト」を状態にして、店を1つずつ追加しながら更新すると解けます。

考察

この問題の本質は次の2点です。

  • 各店のパックは何個でも買える(個数制限なし)
  • 目標は「ちょうど \(D\) 日」ではなく「\(D\) 日以上」

素朴に「各店で何個買うか」を全探索すると、組み合わせ数が爆発して現実的ではありません。
また、日数は最大 \(3000\) なので、日数を軸にしたDPが有効です。

ここで
dp[d] = これまで見た店だけを使って、d日以上を賄う最小コスト
と定義すると、答えは最終的に dp[D] です。

「以上」を扱うために、遷移で d - f < 0 のとき 0 に丸めるのがポイントです。
これは「1パックで必要日数を超えたら、残り必要日数は0」という意味です。


なぜ new_dp を使うのか?

  • 店を1つ処理するとき、その店を複数回使える必要がある
  • そのため、同じ店の更新結果をさらに使って更新できる形にする

コードでは cand = new_dp[max(0, d-f)] + c としていて、右辺に new_dp を使っているため、同一店の複数回購入が自然に表現されています。
一方で new_dp の初期値を dp[:] にしているので、「その店を使わない」選択肢も残ります。

アルゴリズム

  1. dp 配列を長さ D+1 で用意し、初期値は INF。dp[0]=0。
  2. 各店 (c, f) について:
    • new_dp = dp[:](この店を使わない場合を引き継ぐ)
    • d = 1..D について
      • prev = max(0, d-f)
      • new_dp[d] = min(new_dp[d], new_dp[prev] + c)
    • dp = new_dp
  3. 最後に dp[D] を出力。

イメージ例

例えば d=7, f=3 のとき、1パック買うと残り必要日数は 4。
さらに同じ店をもう1個買うなら、new_dp[4] から遷移できるので、同一店の複数回購入が反映されます。

計算量

  • 時間計算量: \(O(ND)\)
  • 空間計算量: \(O(D)\)

実装のポイント

  • INF は十分大きく(例: 10**30)してオーバーフロー的な不具合を避ける。

  • prev = max(0, d-f) として「\(D\) 日以上」を正しく扱う。

  • 無制限個の遷移にするため、遷移元は dp ではなく new_dp を使う。

    ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())

    INF = 10**30
    dp = [INF] * (D + 1)
    dp[0] = 0

    for _ in range(N):
        c, f = map(int, input().split())
        new_dp = dp[:]  # use this shop in addition to previous shops (unbounded)
        for d in range(1, D + 1):
            prev = d - f
            if prev < 0:
                prev = 0
            cand = new_dp[prev] + c
            if cand < new_dp[d]:
                new_dp[d] = cand
        dp = new_dp

    print(dp[D])

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。