No.317

まずは Union-Find で各連結部分の頂点数を計算する.

そうすると, 問題は「$a_i$ 円のコインを使って $n$ 円を作るときの最小の硬貨の枚数を求めよ」と同じ問題となる. (追加する辺の数は (硬貨の枚数 - 1) となるがこれは最後に引けばいい)

これはナップザック問題であるが, 普通の DP を使うと硬貨の枚数が最大 $N$ 枚であるので, 計算量が $O(N^2)$ となって間に合わない.

そこで, 「$a_i$ 円のコインが $c_i$ 枚あり, これを使って $n$ 円を作るための最小の硬貨の枚数を求める」と問題を読み替える. 硬貨の種類は $1,2,3, \dots$ 円となるときに最大になるので, $\sqrt{N}$ 種類程度になる.

このとき, $j$ 種類まで使ったときに $k$ 円を作るための最小の硬貨の枚数を $D(j, k)$ とすると, 漸化式は,

$$D(j+1, k) = \min(D(j, k), D(j, k-a_j) + 1, D(j, k-2a_j) + 2, \dots, D(j, k-c_ja_j) + c_j)$$

となる. これを素直に計算すると $j$ ごとに $O(N^2)$ かかってしまう. そこで $m = 0 \dots a_j-1$ ごとに,

$${ D(j, m), D(j, m+a_j) - 1, D(j, m+2a_j) - 2, \dots }$$

の配列を作っておく. この配列を使ってスライド最小値の要領で $k$ ごとの最小値の計算をすれば, $j$ ごとの計算量を $O(N)$ に抑えることができ, 硬貨の種類数は $\sqrt{N}$ 程度であるので, 全体の計算量を $O(N\sqrt{N})$ に抑えることができる.

ただし, このやり方を枚数の少ない硬貨でやると定数倍が大きいので, 枚数の少ない硬貨については普通の DP を使う.