Official

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個追加する操作」を何度も繰り返せるため、無制限に購入可能という条件を自然に表現できています。

アルゴリズム

  1. \(dp\) 配列を長さ \(D+1\) で用意する。
    • \(dp[d]\) : ちょうど \(d\) 日分を賄う最小金額
    • ただし \(dp[D]\) は「\(D\) 日以上を賄う最小金額」
  2. 初期値は
    • \(dp[0] = 0\)
    • それ以外は十分大きい値(\(\infty\))
  3. \(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)\)
  4. 最後に \(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 によって生成されました。