Official

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

gpt-5.3-codex

Overview

Since you can buy any number of food packs at each store, this is an unbounded knapsack minimization DP.
It can be solved by defining the state as “the minimum cost to cover at least \(d\) days in total” and updating as we add stores one by one.

Key Observations

The essence of this problem lies in two points:

  • Each store’s pack can be bought any number of times (no limit on quantity)
  • The goal is not “exactly \(D\) days” but “at least \(D\) days”

Naively enumerating “how many to buy at each store” leads to a combinatorial explosion and is not practical.
Also, since the number of days is at most \(3000\), a DP with days as the axis is effective.

Here we define:
dp[d] = the minimum cost to cover at least d days using only the stores seen so far
The answer is ultimately dp[D].

To handle “at least,” the key point is to round d - f to 0 when it becomes negative.
This means “if a single pack exceeds the required number of days, the remaining required days is 0.”


Why use new_dp?

  • When processing one store, we need to be able to use that store multiple times
  • Therefore, we need a form where we can further update using the results of updates from the same store

In the code:
cand = new_dp[max(0, d-f)] + c
Since the right-hand side uses new_dp, purchasing the same store’s pack multiple times is naturally represented.
Meanwhile, since the initial value of new_dp is set to dp[:], the option of “not using this store” is also preserved.

Algorithm

  1. Prepare a dp array of length D+1, initialized to INF. Set dp[0]=0.
  2. For each store (c, f):
    • new_dp = dp[:] (carry over the case of not using this store)
    • For d = 1..D:
      • prev = max(0, d-f)
      • new_dp[d] = min(new_dp[d], new_dp[prev] + c)
    • dp = new_dp
  3. Output dp[D] at the end.

Illustrative Example

For example, when d=7 and f=3, buying one pack leaves a remaining requirement of 4 days.
If we buy another pack from the same store, we can transition from new_dp[4], so multiple purchases from the same store are properly reflected.

Complexity

  • Time complexity: \(O(ND)\)
  • Space complexity: \(O(D)\)

Implementation Notes

  • Set INF to a sufficiently large value (e.g., 10**30) to avoid overflow-like issues.

  • Use prev = max(0, d-f) to correctly handle “at least \(D\) days.”

  • To enable unlimited purchases, use new_dp (not dp) as the transition source.

    Source Code

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()

This editorial was generated by gpt-5.3-codex.