AtCoder Regular Contest 067 E. Grouping

もしかしてなんですけどmaroon君が苦手ですか？maroon君がセッターの時は出ないようにします。

問題

読めばええ: E - Grouping

解法

まあどう見てもDP。

初め人を区別しないと思っていて(どうして？)、詰んだ。

というより全然違う立式をしていた。

人を区別しない時の式はかなりシンプルで、

になるので、dp[i][j]をdp[i][j-i]から計算できてO(N^3)からO(N^2)に落ちるねとなる。

これで書き上げてサンプルを試した所で人を区別することに気づく、頭が悪い。

そこから式を書き直した。

前の方針に引きずられて、同じ感じでO(N^2)に落としてやろうとしたんだけど、上手くいかない。というのは、どうしても、dp[i][j-i]を使いまわそうとした時に、Σの中の項に掛けるべき定数にkが残るから。

辛いなあと思っていたんだけど、よくよく考えると、「1/(k!) Π ~」の部分は、P(n+ik-j, ik) /(k! * (i!)^k)で書き換えられるなあという気持ちになって(P(n, k)はn個からk個選択して順列を作る場合の数)、その上「C ≦ k ≦ min(D, j/i)」だなあと思って、あれシグマの中身の計算O(NlogN)回で抑えられるじゃん(よくある区分求積を考えれば自明な奴)となってO(N^2logN)になって終わった。

引きずられたのもどうかと思うし流石にこういう典型が解けないのは反省したい....