この問題は DP により解くことができます。

\(\mathrm{DP}[i][w]\) を 「 \(i\) 種類目の紐までを使って長さ \(w\) のロープを作るときの本数の最小値」とします。

この DP は \(i\) 種類目の紐を何本使うかを考えることで、

\(\mathrm{DP}[i][w]=\min\{\mathrm{DP}[i-1][w-kL_i]+k \mid 0 \leq k \leq \min(w/L_i, C_i)\}\)

として計算することができますが、この式の通りに計算すると \(W^2\log N\) 程度の時間がかかり、実行時間制限に間に合わせることは困難です。

方針1： 2ベキに分解

ある種類の紐が \(20\) 本あるとします。この \(20\) 本の紐を \(1,2,4,8,5\) 本の \(5\) つのグループに分けると、これら \(5\) つのグループの組み合わせで、\(0\) 本から \(20\) 本まで全てを作ることができます。

このようにして、全ての種類の紐をそれぞれいくつかのグループに分解し、改めてインデックスを振り直すことで問題は「長さ \(L_i\) の紐 \(C_i\) 本からなるグループがある。各グループを使うか使わないか選んで、長さの合計を \(W\) にするとき、紐の本数の最小値は？」となります。

これは \(\mathrm{DP}[i][w]\) を「 \(i\) 番目のグループまでを使って長さ \(w\) のロープを作るときの本数の最小値」として

\(\mathrm{DP}[i][w]=\min(\mathrm{DP}[i-1][w], \mathrm{DP}[i-1][w-L_iC_i]+C_i)\)

と計算することができます。1 種類の紐からグループは \(O(\log C_i)\) 個できるため、この DP は状態数 \(O(NW\log C_i)\) 、遷移 \(O(1)\) であり、全体で \(O(NW\log C_i)\) 時間でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, w;
  cin >> n >> w;
  map<int, int> d;
  for(int i=0; i<n; i++){
    int l, c;
    cin >> l >> c;
    d[l] += c;
  }

  int INF = 1e9;
  vector<int> dp(w+1, INF);
  dp[0] = 0;
  for(auto [l, c]: d){
    int k = 1;
    while (c > 0){
      k = min(k, c);
      for(int i=w; i>=(long long)k*l; i--){
        dp[i] = min(dp[i], dp[i-k*l] + k);
      }
      c -= k;
      k *= 2;
    }
  }

  if(dp[w] == INF){
    cout << -1 << endl;
  }else{
    cout << dp[w] << endl;
  }
}

実装例 (Python)

from collections import defaultdict
N, W = map(int, input().split())
d = defaultdict(int)
for _ in range(N):
  l, c = map(int, input().split())
  d[l] += c

INF = 10**18
dp = [INF] * (W+1)
dp[0] = 0
for l, c in d.items():
  k = 1
  while c:
    k = min(k, c)
    for i in range(W, k*l-1, -1):
      dp[i] = min(dp[i], dp[i-k*l] + k)
    c -= k
    k *= 2

if dp[W] == INF:
  print(-1)
else:
  print(dp[W])

方針2： \(L_i\) で割った余りで場合分け

冒頭で挙げたDPの遷移式

\(\mathrm{DP}[i][w]=\min\{\mathrm{DP}[i-1][w-kL_i]+k \mid 0 \leq k \leq \min(w/L_i, C_i)\}\)

を、\(w\) を \(L_i\) で割った余りに着目し次のように変形します。

\(\begin{aligned} \mathrm{DP}[i][qL_i+r] &= \min\{\mathrm{DP}[i-1][kL_i+r]+(q-k) \mid q-C_i \leq k \leq q\}\\ &= q+\min\{\mathrm{DP}[i-1][kL_i+r]-k \mid q-C_i \leq k \leq q\} \end{aligned}\)

\(q\) を動かすことを考えると、右辺の min の計算は数列 \((\mathrm{DP}[i-1][r], \mathrm{DP}[i-1][L_i+r]-1,\mathrm{DP}[i-1][2L_i+r]-2,\ldots)\) のスライド最小値となることがわかります。よって、適切な実装により、\(0 \leq q \leq Q\) の範囲の全ての \(q\) に対する \(\mathrm{DP}[i][qL_i+r]\) を \(O(Q)\) で求めることができます。

これを各 \(r\) に対して行うことで \(\mathrm{DP}[i-1]\) から \(\mathrm{DP}[i]\) を得ることが \(O(W)\) ででき、全体で \(O(NW)\) でこの問題を解くことができます。