C - 食料の買い出し / Grocery Shopping Editorial by admin
GPT 5.4 High概要
この問題は、「各食料パックを何個でも買える」という条件のもとで、合計 \(D\) 日以上を賄うための最小費用を求める問題です。
\(dp[d] =\)「ちょうど \(d\) 日分(ただし \(d=D\) は \(D\) 日以上)を賄う最小金額」とする動的計画法で解けます。
考察
まず、各店の食料パックは何個でも買えるので、これは 個数無制限ナップサック に近い問題です。
重要な気づき
欲しいのは「何円使ったか」ではなく、「何日分を確保できたか」です。
そこで、
- 何日分を確保したかを状態にする
- そこに食料パックを 1 個追加していく
という形で考えると自然です。
具体的には、
- \(dp[d]\) : 現時点で合計 \(d\) 日分を賄うための最小金額
とします。
ただし、問題では「\(D\) 日以上」でよいので、\(d+F_i\) が \(D\) を超えたらすべて \(D\) にまとめてしまえば十分です。
つまり遷移先は
\[ nd = \min(D, d + F_i) \]
です。
素朴な方法が難しい理由
1. 全組み合わせを試すのは不可能
各店から何個でも買えるので、購入パターンは無数にあります。
当然、全探索はできません。
2. 「1日あたりの値段」が安い店を貪欲に選んでもダメ
たとえば、\(C_i / F_i\) が最小の店をひたすら選べばよさそうに見えますが、
実際には「端数」や「超過してよい」という条件があるため、最適にならないことがあります。
例えば、
- パックA: 3日分で4円
- パックB: 5日分で7円
- \(D=6\)
のとき、単純な比率だけでは判断できません。
こうした問題は、局所的な良さだけでは最適解が決まらないため、DPが有効です。
どう解決するか
\(D \le 3000\) なので、日数を状態にした DP が十分間に合います。
各状態 \(d\) から、各店のパックを 1 個買うことを考えると、
\[ dp[\min(D, d+F_i)] = \min(dp[\min(D, d+F_i)],\ dp[d] + C_i) \]
という遷移ができます。
これを \(d=0,1,2,\dots,D-1\) について順に行えば、
最終的な \(dp[D]\) が答えになります。
なぜこれで「何個でも買える」を表せるのか
一見すると「各店を1回ずつしか見ていない」ように感じるかもしれませんが、そうではありません。
状態 \(d\) からある店のパックを 1 個買って \(d+F_i\) に進み、
さらにその状態から同じ店のパックをもう 1 個買う、ということができます。
つまり「1個追加する操作」を何度も繰り返せるため、無制限に購入可能という条件を自然に表現できています。
アルゴリズム
- \(dp\) 配列を長さ \(D+1\) で用意する。
- \(dp[d]\) : ちょうど \(d\) 日分を賄う最小金額
- ただし \(dp[D]\) は「\(D\) 日以上を賄う最小金額」
- 初期値は
- \(dp[0] = 0\)
- それ以外は十分大きい値(\(\infty\))
- \(d=0\) から \(D-1\) まで順に見る
- もし \(dp[d]\) が未到達ならスキップ
- 各店 \((C_i, F_i)\) について
- \(nd = \min(D, d + F_i)\)
- \(dp[nd] = \min(dp[nd], dp[d] + C_i)\)
- 最後に \(dp[D]\) を出力する
具体例
例えば \(D=7\)、店が
- \((C,F)=(3,2)\)
- \((5,4)\)
の2つだとします。
- \(dp[0]=0\)
- \(0\) 日から
- 2日分に 3円
- 4日分に 5円
- 2日分からさらに
- 4日分に 6円
- 6日分に 8円
- 4日分からさらに
- 6日分に 8円
- 7日以上に 10円
というふうに更新していき、最終的に \(dp[7]\) が最小費用になります。
計算量
- 時間計算量: \(O(ND)\)
- 空間計算量: \(O(D)\)
\(N,D \le 3000\) なので、\(O(ND)=9 \times 10^6\) 程度で十分高速です。
実装のポイント
「\(D\) 日以上」を扱うため、遷移先は必ず $\( \min(D, d+F_i) \)\( として、\)D$ を超えた分をまとめます。
初期値には十分大きい値として
10**18を使っています。dp[d]が未到達(INF)のときは遷移しないようにすると無駄な計算を避けられます。この実装では、外側を日数
d、内側を店にしており、
「今の状態からパックを1個追加する」という形で自然に無制限購入を表現しています。ソースコード
import sys
def main():
input = sys.stdin.readline
N, D = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)] # (C, F)
INF = 10**18
dp = [INF] * (D + 1)
dp[0] = 0
for d in range(D):
if dp[d] == INF:
continue
cur = dp[d]
for c, f in items:
nd = D if d + f >= D else d + f
if dp[nd] > cur + c:
dp[nd] = cur + c
print(dp[D])
if __name__ == "__main__":
main()
この解説は gpt-5.4-high によって生成されました。