概要

在庫数制限つきのナップサック（重さは「ちょうど \(S\)」）で、達成可能なら満足度合計の最大値を求める問題です。到達不能なら -1 を出力します。

考察

これは典型的な 個数制限付き（bounded）ナップサックです。
状態として「重さ \(x\) を作るときの満足度最大」を持てばよいですが、素朴に

• 各商品 \(i\) について
• 現在の重さ \(x\) について
• 個数 \(k=0..c_i\) を試す

とすると、計算量が \(O\!\left(\sum_i S\cdot c_i\right)\) になり、\(c_i\) が最大 \(10^5\) なので確実に TLE します。

そこで、各商品の更新 [ dp{\text{new}}[x] = \max{0\le t\le c}{dp[x-tw] + tv} ] を高速化します。ポイントは、重さ \(x\) を \(w\) で割った 余りごとに分けることです。

\( x = r + kw \ (0\le r < w)\) と書くと [ dp{\text{new}}[r+kw] = \max{0\le t\le c}{dp[r+(k-t)w] + tv}. ] ここで \(j=k-t\) と置くと（つまり「前の状態の段数」） [ dp{\text{new}}[r+kw] = \max{k-c \le j \le k}{dp[r+jw] + (k-j)v}. ] さらに整理して [ dp{\text{new}}[r+kw] = kv + \max{k-c \le j \le k}{dp[r+jw] - jv}. ] つまり、各 \(k\) で必要なのは区間 \([k-c,\,k]\) の [ A_j = dp[r+jw] - jv ] の最大値です。これは スライディングウィンドウ最大なので、単調キュー（deque）で \(O(1)\) amortized で更新でき、各商品あたり全体で \(O(S)\) にできます。

アルゴリズム

• \(dp[x]\) を「重さ合計がちょうど \(x\) のときの満足度最大」とする。
  • 到達不能は十分小さい値（コードでは NEG）で表す。
  • 初期値：\(dp[0]=0\)、それ以外は NEG。
• 各商品 \((w,v,c)\) について次を行う：
  • 新しい配列 \(dp\_new\) を NEG で初期化。
  • 余り \(r=0..w-1\) ごとに、\(x=r+kw\)（\(k=0,1,2,\dots\)）を昇順に走査する。
    • deque には候補 \(j\) とその値 \(A_j = dp[r+jw]-jv\) を「値が大きい順」になるように保持する。
    • \(k\) を進めるたびに：
      1. 現在の \(j=k\) を候補として deque に追加（到達可能なときのみ）。
      2. 窓の範囲外（\(j < k-c\)）を deque の先頭から削除。
      3. deque の先頭が \(\max A_j\) なので [ dp_new[r+kw] = (\max A_j) + kv ] とできる。
• 最後に \(dp[S]\) が NEG なら -1、そうでなければその値を出力。

この方法により、「個数 \(0..c\) を全部試す」部分を、余りごとの単調キューでまとめて処理できます。

計算量

• 時間計算量: \(O(N\cdot S)\)
  （各商品につき、\(0..S\) の各重さを高々定数回 deque 操作で処理）
• 空間計算量: \(O(S)\)
  （\(dp\) と \(dp\_new\) の2本）

実装のポイント

• 到達不能の管理が重要です。NEG（十分小さい値）を使い、dp[pos] != NEG のときだけ deque に追加します。

• 余り \(r\) ごとに \(pos=r+kw\) を増やすことで、「同じ余りの列」だけを見ればよくなり、式変形が成立します。

• deque には (j, A_j) を入れ、末尾から「値が小さい（または同じ）候補」を削って単調性を保ちます（最大値が先頭に来る）。
  

• 窓幅は「最大 \(c\) 個まで」なので、\(j < k-c\) を先頭から捨てることで個数制限を守ります。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline
    N, S = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    NEG = -10**18
    dp = [NEG] * (S + 1)
    dp[0] = 0

    for w, v, c in items:
        dp_new = [NEG] * (S + 1)
        for r in range(w):
            dq = deque()
            k = 0
            while True:
                pos = r + k * w
                if pos > S:
                    break

                base = dp[pos]
                if base != NEG:
                    cand = base - k * v
                    while dq and dq[-1][1] <= cand:
                        dq.pop()
                    dq.append((k, cand))

                lim = k - c
                while dq and dq[0][0] < lim:
                    dq.popleft()

                if dq:
                    dp_new[pos] = dq[0][1] + k * v

                k += 1
        dp = dp_new

    ans = dp[S]
    print(ans if ans != NEG else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。