分割数 DP について

昨日の第4回ドワンゴからの挑戦状予選 C 問題で、分割数 DP を必要とする問題が出されました。

蟻本をよく読んでいる人ならご存知のとおり、この DP は dp[i][j] := j を i 分割する時の場合の数 とするとき、 dp[i][j] = dp[i][j-i] + dp[i-1][j] となります。しかし、蟻本の解説だけだとどうもわかりにくいです (少なくとも自分は理解するまでに N 時間かかりました)。

というわけで、ドワコンのあいだに実際に私が考察した、蟻本とは違うアプローチ (本質的には同じ) でこの式を導出してみます。

若干遅い解法

まず、なにを解きたいのかをちゃんと式で書きましょう。ちゃんと書くと、以下のようになります。

$N$ の $M$ 分割 $( dp\left[ M \right] \left[ N \right] )$ → $a_{1} \leq a_{2} \leq \dots \leq a_{M}, \sum_{k=1}^{M} a_{k} = N$ を満たす数列 $\left\{ a \right\}$ の総数

まず、 $1$ 番目の要素 $a_{1}$ の値を $x$ にすることを考えましょう。 $a_{1}$ は他のどの値よりも小さいか等しいため、 $a_{2}, a_{3}, \dots, a_{M}$ は必ず $x$ 以上の値を取ります。

$1$ 番目の値を確定させると、残った $(M-1)$ 個の要素に対して同様に分割数 DP を適用すれば良いことが分かります。このとき、各要素は必ず $x$ 以上の値をとるのですから、全ての要素から $x$ 引いて考えても問題ありません。

以上のことから、以下のような DP が立てられます。

$dp\left[ i \right] \left[ j \right] = \sum_{x=0}^{\lfloor \frac{j}{i} \rfloor} dp\left[ i-1 \right] \left[ j-i*x \right]$

見た目でわかるとおり、これを実装すると 3 重ループになります。 $\sum_{k=1}^{M} \frac{1}{k} \approx \log M$ という近似より、計算量はたぶん $O(NM \log M)$ です (間違っていたら教えてください)。実際にドワコンの問題でこの漸化式を使っても通るのですが、次に説明する工夫をすることで log を取ることができます。

速い解法へ

基本的には、先ほどの式を応用させるイメージでやります。式を再掲します。

$dp\left[ i \right] \left[ j \right] = \sum_{x=0}^{\lfloor \frac{j}{i} \rfloor} dp\left[ i-1 \right] \left[ j-i*x \right]$

$j-i*x$ という部分に着目します。 $i, j$ を定数としてみたとき、 $j$ から $i$ の倍数を引いていることが分かります。ここで、おもむろに $x = 0$ の部分だけシグマから抜き出します。

$dp\left[ i \right] \left[ j \right] = \sum_{x=1}^{\lfloor \frac{(j-i) + i}{i} \rfloor} dp\left[ i-1 \right] \left[ (j-i) - i*(x-1) \right] + dp\left[ i-1 \right] \left[ j \right]$

ここで、 $j' = j-i, x' = x-1$ とおくと、

\begin{align} dp\left[ i \right] \left[ j \right] &= \sum_{x'=0}^{\lfloor \frac{j'}{i} \rfloor} dp\left[ i-1 \right] \left[ j'- i*x' \right] + dp\left[ i-1 \right] \left[ j \right] \\ &= dp\left[ i \right] \left[ j' \right] + dp\left[ i-1 \right] \left[ j \right] \\ &= dp\left[ i \right] \left[ j-i \right] + dp\left[ i-1 \right] \left[ j \right] \end{align}

このように変形できて、無事 $O(NM)$ になりました。終わり！ (雑)