概要

長さが決まった複数種類の紐を在庫数の範囲で選び、合計長さをちょうど \(W\) にしつつ使用本数を最小化する（作れないなら \(-1\)）問題です。

考察

これは「個数制限付きナップサック（bounded knapsack）」で、価値ではなく 本数（コスト）を最小化し、合計長さを ちょうど \(W\) にする問題です。

• 状態として「長さ \(x\) を作る最小本数」を持つと自然です。
• ただし素朴に各種類ごとに
  • \(k=0..C_i\) 本使う場合を全探索して遷移（\(O(W\sum C_i)\)）
  • あるいは \(C_i\) 回の 0/1 ナップサックに分解（これも重い）

とすると、\(W\le 50000\)・\(C_i\le 10000\) のため間に合いません。

ここで重要な観察は、ある長さ \(L\) の紐だけを見ると遷移は

[ dp’[x] = \min_{0 \le k \le C,\ x-kL\ge 0}{dp[x-kL] + k} ]

となり、同じ \(L\) では \(x\) を \(L\) で割った余りごと（\(x\equiv r\pmod L\)）に独立に処理できることです。
この「余りごとの列」に対して、スライド最小値（単調キュー）を使うと \(O(W)\) で更新できます。

また、入力には「同じ長さの種類」があり得るので、先に長さごとに在庫数を合算しておくと種類数が減り、実装も簡単になります。

アルゴリズム

1. DP 定義

• \(dp[x]\)：合計長さをちょうど \(x\) にするための最小本数（不可能なら \(\infty\)）
• 初期値：\(dp[0]=0,\ dp[1..W]=\infty\)

2. 長さ \(L\)・在庫 \(C\) の更新（単調キュー最適化）

遷移は

[ dp’[x] = \min_{k}{dp[x-kL] + k} ]

ですが、\(x=r+mL\) とおき（\(r\) は \(0..L-1\)）、\(m\) を増やしながら見ると

[ dp’[r+mL] = \min_{t \in [m-C,\ m]}{dp[r+tL] + (m-t)} ]

右辺を変形して

[ dp’[r+mL] = m + \min_{t \in [m-C,\ m]}{dp[r+tL] - t} ]

となります。つまり、各余り \(r\) について列 [ A[t] = dp[r+tL] - t ] の 幅 \((C+1)\) の区間最小値を順に求めればよいです。

そこで各 \(r\) ごとに deque（単調キュー）を使い、

• deque には候補 \((t, A[t])\) を \(A[t]\) が小さい順になるように保持
• 範囲外（\(t < m-C\)）は先頭から捨てる
• 先頭が常に区間最小

として \(dp'[r+mL] = m + \text{(先頭の }A[t]\text{)}\) を \(O(1)\) 償却で計算します。

3. 答え

全種類処理後、\(dp[W]\) が \(\infty\) なら \(-1\)、そうでなければ \(dp[W]\) を出力します。

計算量

• 時間計算量: \(O(W \cdot M)\)（\(M\) は「長さが異なる種類数」。各種類につき全 \(x=0..W\) を合計 \(O(W)\) で処理）
• 空間計算量: \(O(W)\)（\(dp\) 配列）

実装のポイント

• 同じ長さは在庫数を合算する（cnt_by_len[L] += C）。これで無駄なループが減ります。

• 「不可能」を表すために十分大きい値 INF を使い、最後に dp[W] が INF かで判定します。

• 単調キューの管理は以下の2点が重要です。

  • 末尾から「値が悪い（大きい）候補」を削除して単調性を保つ

  • 先頭から「在庫制限で使えない範囲外」を削除する（t < m-C を捨てる）

    ソースコード

import sys
from collections import defaultdict, deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    W = int(next(it))

    cnt_by_len = defaultdict(int)
    for _ in range(N):
        L = int(next(it))
        C = int(next(it))
        cnt_by_len[L] += C

    items = sorted(cnt_by_len.items())  # (L, C)

    INF = 10**18
    dp = [INF] * (W + 1)
    dp[0] = 0

    for L, C in items:
        new_dp = [INF] * (W + 1)
        for r in range(L):
            dq = deque()  # (m, dp[r+mL] - m)
            m = 0
            x = r
            while x <= W:
                val = dp[x] - m
                while dq and dq[-1][1] >= val:
                    dq.pop()
                dq.append((m, val))
                while dq[0][0] < m - C:
                    dq.popleft()
                new_dp[x] = dq[0][1] + m
                m += 1
                x += L
        dp = new_dp

    ans = dp[W]
    print(-1 if ans >= INF // 2 else ans)

if __name__ == "__main__":
    main()

---

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