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[:] にしているので、「その店を使わない」選択肢も残ります。
アルゴリズム
dp配列を長さD+1で用意し、初期値はINF。dp[0]=0。- 各店
(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
- 最後に
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 によって生成されました。