概要

\(N\) 種類の紐（長さ \(L_i\)、在庫 \(C_i\) 本）を組み合わせて、合計の長さをちょうど \(W\) センチメートルにするために必要な「最小の本数」を求める問題です。

考察

この問題は、典型的な「個数制限付きナップサック問題」の最小化バージョンです。

素朴なアプローチ

動的計画法（DP）を用いることを考えます。 \(dp[i][j]\) を「 \(i\) 番目までの紐を使って長さ \(j\) を作るための最小本数」と定義すると、遷移式は以下のようになります。 \(dp[i][j] = \min_{0 \le k \le C_i} \{ dp[i-1][j - k \cdot L_i] + k \}\)

しかし、この遷移をそのまま実装すると、各 \(j\) に対して \(C_i\) 回の比較が必要になります。最悪の場合、計算量は \(O(W \cdot \sum C_i)\) となり、本問題の制約（\(W=50000, C_i=10000\)）では実行時間制限に間に合いません。

高速化のヒント

遷移式をよく見ると、長さ \(j\) を \(L_i\) で割った「余り」が同じ位置からのみ遷移していることがわかります。 例えば、長さ \(L_i=3\) の紐を使う場合、余りが \(0\) の位置（\(0, 3, 6, \dots\)）はそれらの中だけで更新し合い、余りが \(1\) の位置（\(1, 4, 7, \dots\)）とは干渉しません。

そこで、余り \(r \in \{0, 1, \dots, L_i-1\}\) ごとに独立して計算を行います。 \(j = q \cdot L_i + r\) とおくと、遷移式は以下のように変形できます。 \(dp[r + q \cdot L_i] = \min_{q - C_i \le p \le q} \{ dp[r + p \cdot L_i] + (q - p) \}\) \(dp[r + q \cdot L_i] = \min_{q - C_i \le p \le q} \{ dp[r + p \cdot L_i] - p \} + q\)

この式の \(\min\) の中身 \(\{ dp[r + p \cdot L_i] - p \}\) は、特定の範囲（ウィンドウ）内での最小値を求める形式になっています。これは「スライド最小値」のアルゴリズムを用いることで、各 \(q\) に対してならし \(O(1)\) で計算可能です。

アルゴリズム

スライディングウィンドウを用いた DP

1. DPテーブルを \(dp[0]=0\)、それ以外を無限大（\(\infty\)）で初期化します。
2. 各紐の種類 \(i=1 \dots N\) について、以下の処理を行います。
   • 長さ \(L_i\) で割った余り \(r = 0, \dots, L_i-1\) ごとにグループ化します。
   • 各グループ内で、両端キュー（deque）を用いて「スライド最小値」を求めます。
   • deque には、値 \(dp[r + p \cdot L_i] - p\) が最小となるようなインデックス \(p\) を、値が昇順になるように保持します。
   • ウィンドウの左端が \(q - C_i\) を超えたら、古い要素を deque から取り除きます。
3. 最終的な答えは \(dp[W]\) です。一度も到達できなければ \(-1\) を出力します。

計算量

• 時間計算量: \(O(NW)\)
  • 各紐の種類について、長さ \(W\) の配列を定数回走査するため、在庫数 \(C_i\) に依存しない計算量となります。
• 空間計算量: \(O(W)\)
  • 1次元の DP 配列を使い回すことで節約可能です。

実装のポイント

• 特殊ケースの最適化:

  • \(C_i = 1\) の場合は「0/1ナップサック問題」として後ろから更新することで高速化できます。
  • \(C_i \ge W/L_i\) の場合は「個数無制限ナップサック問題」として前から更新することで高速化できます。

• Pythonでの高速化:

  • collections.deque を使用し、さらに append や pop などのメソッドをローカル変数にキャッシュすることで、ループ内のオーバーヘッドを減らすことができます。

  • dp[r::L] のようなスライス表記を用いると、特定の余りの要素を効率的に抽出・更新できます。

    ソースコード

import sys
from collections import deque

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to efficiently traverse the input data
    it = iter(input_data)
    N = int(next(it))
    W = int(next(it))
    
    # dp[j] stores the minimum number of strings to reach a total length of j
    INF = 10**9
    dp = [INF] * (W + 1)
    dp[0] = 0
    
    for _ in range(N):
        L = int(next(it))
        C = int(next(it))
        
        # If the string length is greater than the target W, it cannot be used
        if L > W:
            continue
        
        # Optimization for special cases of the Bounded Knapsack Problem
        if C == 1:
            # 0/1 Knapsack optimization: iterate backwards to reuse results from previous items
            for j in range(W, L - 1, -1):
                new_val = dp[j - L] + 1
                if new_val < dp[j]:
                    dp[j] = new_val
        elif C >= W // L:
            # Unbounded Knapsack optimization: iterate forwards to allow using the same item multiple times
            for j in range(L, W + 1):
                new_val = dp[j - L] + 1
                if new_val < dp[j]:
                    dp[j] = new_val
        else:
            # General Bounded Knapsack using a sliding window (monotonic queue) for O(NW) total complexity
            for r in range(L):
                # If the remainder r + L exceeds W, this slice will only contain one element which cannot be updated
                if r + L > W:
                    break
                
                # Extract the relevant slice of dp values for the current remainder r
                old_vals = dp[r::L]
                n_q = len(old_vals)
                new_vals = [INF] * n_q
                deq = deque()
                
                # Cache deque methods for slight performance gain in Python
                deq_append = deq.append
                deq_pop = deq.pop
                deq_popleft = deq.popleft
                
                for q in range(n_q):
                    ov_q = old_vals[q]
                    # Only add reachable states to the deque
                    if ov_q < INF:
                        # We want to minimize (dp[r + p*L] - p) + q
                        val = ov_q - q
                        # Maintain the deque such that values are in non-decreasing order
                        while deq and deq[-1][0] >= val:
                            deq_pop()
                        deq_append((val, q))
                    
                    # Ensure the current string count (q - p) does not exceed the stock count C
                    if deq and deq[0][1] < q - C:
                        deq_popleft()
                    
                    # Update new_vals with the minimum found in the current window
                    if deq:
                        new_vals[q] = deq[0][0] + q
                
                # Assign the updated slice back to the main dp array
                dp[r::L] = new_vals
                
    # Final answer: if dp[W] is still INF, it's impossible to form exactly W cm
    ans = dp[W]
    if ans >= INF:
        print("-1")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。