分割数のDPをO(Nsqrt(N))でやる

Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。

• 問題

分割数の N 番目を求めよ。

• 解法

まず、DP[N][K]: K個の和でNを作る場合の数 とする。
1を使う場合と使わない場合に分けると、DP[N][K]=DP[N-1][K-1]+DP[N-K][K] がわかる。このままやると O(N^2) となる。

B=floor(sqrt(N))として、K < B に対して、この DP を愚直に計算する。

K>=B に対しては、x[s][t]: B<=xに対する DP[s-tx][x] たちの和 とする。下の図の青線や緑線一本一本の和を、始点と傾きを変えながら全部求めると思えばよい。x[N][0] がわかれば OK 。

このとき、t (すなわち傾き) は、sqrt(N) までしか考えなくてよい。これは、傾きがそれ以上大きいとき、直線は前計算した赤い領域以外の DP 値が 0 でない点を通らないためである。

さて、x[s][t] に対して先ほどの DP の漸化式を項ごとに適用すれば、x[s][t]=(x[s-1-t][t]+DP[s-1][B-1])+x[s-B][t+1] となる。括弧内の項は、DP[N-1][K-1] から DP[N][K] への遷移に対応し、今和を取っている直線を左斜め上 45 度にそのまま移動したものからの遷移を表す。K < B なる領域に踏み込んでいるので、その分は前計算された DP[s-1][B-1] を足しておく。第二項は、DP[N-K][K] から DP[N][K] への遷移に対応し、直線の傾きが 1 だけ増える。

DP[N][K] を K < B に対して前計算しておけば、x[s][t] も全部合わせて O(Nsqrt(N)) で更新できるので、全部合わせて O(Nsqrt(N)) で分割数が計算できたことになる。