hogecoder

tsutaj 競技プログラミングの記録

分割数 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) になりました。終わり! (雑)

ということで、蟻本とは少し違う導出をやりました。