Official

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

Claude 4.6 Opus (Thinking)

概要

\(N\) 個の店から食料パックを自由に(同じ店から何個でも)購入し、合計で \(D\) 日分以上の食事を賄うための最小費用を求める、個数制限なしナップサック問題です。

考察

問題の言い換え

各店 \(i\) の食料パックは「コスト \(C_i\) 円で \(F_i\) 日分の価値がある品物」と見なせます。同じ店から何個でも買えるため、これは典型的な個数制限なしナップサック問題(Unbounded Knapsack Problem)に帰着します。

ただし通常のナップサックは「容量以内で価値を最大化」ですが、今回は逆で「\(D\) 日以上を達成するコストを最小化」する問題です。

素朴なアプローチの問題点

全探索で各店から何個買うかを全通り試すと、各店から最大 \(D / F_i\) 個買う可能性があり、組み合わせが爆発して到底間に合いません。

動的計画法(DP)への落とし込み

\(dp[j]\) = 「ちょうど \(j\) 日分を賄える最小費用」と定義します。ここで \(j\) の上限は \(D\) で十分です。なぜなら、\(D\) 日以上はすべて同じ「\(D\) 日分達成」とみなせるため、\(j + F_i\) が \(D\) を超えた場合は \(\min(j + F_i, D)\) に丸めれば良いからです。

アルゴリズム

  1. \(dp[0] = 0\)、\(dp[1], \dots, dp[D] = \infty\) で初期化する。
  2. 各店 \((C_i, F_i)\) について、\(j = 0, 1, \dots, D\) の順に以下を行う:
    • \(dp[j]\) が \(\infty\) でなければ、\(nj = \min(j + F_i,\ D)\) として \(dp[nj] = \min(dp[nj],\ dp[j] + C_i)\) と更新する。
  3. 最終的に \(dp[D]\) が答え。

なぜ \(j\) を小さい方から走査するのか

個数制限なしナップサックでは、同じ品物を複数回使うことを許すため、\(j\) を昇順に走査します。こうすると、同じ品物による更新結果がさらに後の \(j\) で参照され、結果的に何個でも使えることになります。

具体例: \(D = 6\)、ある店で \(C = 5, F = 3\) の場合 - \(j = 0\): \(dp[3] = \min(\infty, 0 + 5) = 5\)(1個購入) - \(j = 3\): \(dp[6] = \min(\infty, 5 + 5) = 10\)(2個購入)

このように、1回のスキャンで同じ品物を何個でも使った結果が正しく反映されます。

\(\min(j + F_i, D)\) の意味

\(j + F_i > D\) のとき、\(D\) 日を超えた余剰分は不要なので、すべて \(dp[D]\) にまとめます。これにより配列サイズを \(D + 1\) に抑えつつ、「\(D\) 日以上」という条件を正しく扱えます。

計算量

  • 時間計算量: \(O(N \times D)\)
    • 各店(\(N\) 個)について、\(j = 0\) から \(D\) まで走査するため。
    • \(N, D \leq 3000\) なので最大約 \(9 \times 10^6\) 回の操作で十分高速。
  • 空間計算量: \(O(D)\)
    • DP 配列のサイズは \(D + 1\)。

実装のポイント

  • \(\min(j + F_i, D)\) によるキャップ: これを忘れると配列外アクセスになるか、\(D\) を超えた日数を別々に管理する必要が生じ、配列サイズが膨大になります。

  • 昇順ループで個数無制限を実現: 0-1 ナップサック(各品物1個まで)では降順に走査しますが、個数制限なしの場合は昇順にする点が重要な違いです。

  • 初期値の設定: \(dp[0] = 0\)、それ以外は \(\infty\)(到達不可能)とすることで、最小化 DP を正しく動かします。

    ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        c = int(input_data[idx]); idx += 1
        f = int(input_data[idx]); idx += 1
        items.append((c, f))
    
    # Unbounded knapsack-like problem:
    # dp[j] = minimum cost to cover exactly j days (j capped at D)
    # We want dp[D].
    
    INF = float('inf')
    dp = [INF] * (D + 1)
    dp[0] = 0
    
    for c, f in items:
        # Unbounded: process each item with forward loop
        for j in range(D + 1):
            if dp[j] == INF:
                continue
            # Buy k packs of this item; but we can do it incrementally
            # Use standard unbounded knapsack approach
            nj = min(j + f, D)
            if dp[nj] > dp[j] + c:
                dp[nj] = dp[j] + c
        
        # The above only adds one pack per item per pass. For unbounded,
        # we need to allow multiple packs. Let's redo with proper unbounded approach.
    
    # Redo with proper unbounded knapsack
    # For unbounded knapsack: for each item, iterate j from small to large
    dp = [INF] * (D + 1)
    dp[0] = 0
    
    for c, f in items:
        for j in range(D + 1):
            if dp[j] == INF:
                continue
            nj = min(j + f, D)
            if dp[nj] > dp[j] + c:
                dp[nj] = dp[j] + c
    
    # Wait, this processes items one by one and only allows one of each per "layer".
    # For unbounded knapsack we need: for each item, sweep forward allowing multiple uses.
    # The correct approach: iterate over items, and for each item do a forward sweep.
    
    # Actually the above nested loop structure (outer: items, inner: j from 0 to D)
    # only considers using item i after items 1..i-1, and since j goes forward,
    # it does allow multiple copies of item i in one pass. Let me re-examine:
    # When processing item i, j goes 0,1,...,D. If dp[0]=0 and f=3,c=5:
    # j=0: dp[3] = min(INF, 0+5) = 5
    # j=3: dp[6] = min(INF, 5+5) = 10  -- yes, multiple copies work!
    # But the issue is that dp[j] might have been updated by the SAME item in this pass
    # which is exactly what we want for unbounded. So this IS correct for unbounded.
    
    # But there's a subtle issue: nj = min(j+f, D) means different j values map to D,
    # and we might overwrite dp[D] and then not use it further. That's fine.
    
    # Let me redo cleanly:
    dp = [INF] * (D + 1)
    dp[0] = 0
    
    for c, f in items:
        for j in range(D + 1):
            if dp[j] < INF:
                nj = min(j + f, D)
                val = dp[j] + c
                if val < dp[nj]:
                    dp[nj] = val
    
    print(dp[D])

main()

この解説は claude4.6opus-thinking によって生成されました。