概要

\(N\) 種類の紐があり、それぞれ長さ \(L_i\) と在庫数 \(C_i\) が与えられます。これらの紐を何本か選び、長さの合計をちょうど \(W\) にしたいです。使用する紐の本数を最小にする問題です。

考察

この問題は典型的な「制限付き部分和問題」であり、ナップサック問題の一種です。目標は「ちょうど \(W\) の長さ」を作ることで、かつ「使用する紐の本数を最小化」することです。

素朴なDPでの問題点

最も単純な方法は、以下のようなDPを考えることです。

• dp[i][w]：\(i\) 番目までの紐を使って長さ \(w\) を作るのに必要な最小の紐の本数

しかし、この方法では状態数が \(O(N \cdot W)\) となり、制約 \(N \leq 100, W \leq 50000\) のもとでは最大で \(5 \times 10^6\) の状態があり、さらに遷移で在庫数 \(C_i\) をループさせると計算量が爆発します。

多重ナップサックの高速化（バイナリテクニック）

そこで、多重ナップサックの高速化として知られる「バイナリ法（カウンティングテクニック）」を使います。

これは、あるアイテムを \(c\) 個使えるときに、以下のように分解します：

\[ c = 1 + 2 + 4 + \cdots + 2^{k-1} + r \]

ここで、\(1, 2, 4, ..., 2^{k-1}\) は2進数的な個数、\(r\) は残りです。

これにより、\(c\) 回ループする代わりに、\(\log c\) 回の処理で済みます。

例えば、ある長さ5の紐が13本ある場合、

\[ 13 = 1 + 2 + 4 + 6 \]

と分解して、長さ5×1、5×2、5×4、5×6 の「合成されたアイテム」として扱います。

これによって、効率的に遷移を行うことができます。

アルゴリズム

この問題は、多重ナップサック問題を本数最小化にして解く問題です。

DP定義

• dp[w]：長さ \(w\) を作るのに必要な最小の紐の本数
  初期値：dp[0] = 0, それ以外は \(\infty\)

更新方法

各紐 \(i\) に対して、在庫数 \(C_i\) をバイナリ法で分解して、合成アイテムごとにDPを更新します。

具体的には： - add_length = L[i] * k としたとき、 - dp[j] = min(dp[j], dp[j - add_length] + k) （ただし j >= add_length）

この更新を全ての合成アイテムに対して行い、最終的に dp[W] が答えです。

計算量

• 時間計算量: \(O(N \cdot W \cdot \log(\max(C_i)))\)
  • 各アイテムに対して、在庫数を \(\log C_i\) 個の合成アイテムに分解し、それぞれについてDPテーブルを逆順に更新する
• 空間計算量: \(O(W)\)
  • DPテーブルはサイズ \(W+1\) の1次元配列

実装のポイント

• DPテーブルの更新は逆順に行うこと（同じアイテムを複数回使わないようにするため）

• 在庫数のバイナリ分解は k=1 から始めて、count -= k; k *= 2 で進める

• 最終的に dp[W] が未更新（\(\infty\)）なら -1 を出力

  ソースコード

import sys
import heapq
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    W = int(data[idx])
    idx += 1
    
    L = []
    C = []
    for _ in range(N):
        l = int(data[idx])
        idx += 1
        c = int(data[idx])
        idx += 1
        L.append(l)
        C.append(c)
    
    # dp[i] := ロープの長さが i になるのに必要な最小の紐の本数
    # 初期値は無限大、ただし dp[0] = 0
    INF = float('inf')
    dp = [INF] * (W + 1)
    dp[0] = 0
    
    # 各アイテムについて処理
    for i in range(N):
        length = L[i]
        count = C[i]
        
        # カウンティングテクニックによる多重ナップサックの処理
        # count を 1, 2, 4, ... の和に分解して処理
        k = 1
        while k < count:
            # 長さ length*k のアイテムを1つ使うと考える
            add_length = length * k
            # 逆順に更新することで同じアイテムを複数回使わないようにする
            for j in range(W, add_length - 1, -1):
                if dp[j - add_length] != INF:
                    dp[j] = min(dp[j], dp[j - add_length] + k)
            count -= k
            k *= 2
        
        # 残りのcount分を処理
        add_length = length * count
        for j in range(W, add_length - 1, -1):
            if dp[j - add_length] != INF:
                dp[j] = min(dp[j], dp[j - add_length] + count)
    
    result = dp[W]
    if result == INF:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。