問題概要

問題文はこちらを参照してください。

なんというか、こんな発想で問題をシンプルにするんだという問題でした。とても一人では思いつける気がしません。

解法

考え方は、同じ文字が隣り合っている箇所の数が新しい種類の文字を追加することでどのように変化するのかをＤＰで求めるというものです。隣の文字が何かとか、どこで隣り合っているかとかは関係なく、同じ文字が隣り合っている箇所の数だけを気にして、隣り合っている箇所の数が0になるのが答えです。

まず、$freq_1$が$6$、$freq_2$が$1$の例を考えてみます。$a$一種類だけの場合は文字列としてaaaaaaしかないので、同じ文字が隣り合っている箇所は5か所あります。ここに、bという文字列を加えて新たな文字列を作る場合を考えます。このとき、すでにある文字列に新しい文字列を挿入して新たな文字列を生成すると考えると、挿入できる場所はaaaaaaの両端も含めて、7か所(長さ+1)になります。

typicalDPO1

挿入した場所がaとaの間の場合、同じ文字が隣り合っている箇所は1つ減ります。もし、挿入した場所が両端のどちらかだった場合は、同じ文字が隣り合っている箇所は変わらず5のままです。ただ、全体の文字列の長さが1増えるので、次に文字列を挿入できる場所が1つ増えます。

次に、$freq_1$が$6$、$freq_2$が$4$の例を考えてみます。この場合は、bbbbをどういう形で挿入するのかの組み合わせを考えます。

typicalDPO2

これらを挿入した場合に増える同じ文字が隣り合っている箇所の数は、bbbbをいくつに分割するかによって決まります。逆に分割した結果の文字列に関係なく、分割数によってのみ決まるということです。

後は、これらの分割された文字列をすでに同じ文字が隣り合っている箇所に挿入するのか、そうではない場所に挿入するのかによって、最終的に出来上がる文字列で同じ文字が隣り合っている箇所の数を決定することができます。ただし、挿入可能な場所には1つの分割した文字列のみを入れることとしています。

まとめると、長さが$freq[i+1]$の文字列を$k$個に分割すると分割の仕方にかかわらず同じ文字が隣り合っている箇所は$freq[i+1]-k$個になります。

長さが$len[i]$の文字列には$len[i]+1$個の文字列を挿入できる場所があります。

従って、$i$種類目までの文字を使って$j$個の同じ文字が隣り合っている箇所がある長さ$len[i]$の文字列に、$i+1$種類目の文字列を$k(1\le k\le freq[i+1])$個に分割して、そのうち$l(0\le l\le k)$個を同じ文字が隣り合っている場所に入れる(残りは同じ文字が隣り合っていない場所に入れる)ことで、新たにできた文字列に含まれる同じ文字が隣り合っている箇所の数は、$j-l+freq[i+1]-k$個になります。これらの組み合わせを配るＤＰで計算していきます。

漸化式の定義： $$\begin{eqnarray} & & dp[i+1][j-l+freq[i+1]-k]\\ & & += dp[i][j]\cdot {}_{freq[i+1]-1}\mathrm{C}_{k-1}\cdot {}_{j}\mathrm{C}_{l}\cdot {}_{len[i]+1-j}\mathrm{C}_{k-l} \end{eqnarray}$$

$dp[i][j]$：$i$種類目までの文字を使って同じ文字が隣り合っている箇所が$j$個ある文字列の数

$freq[i]$：$i$種類目の文字の使える個数(問題文の$freq_i$が0の部分は除いて考える)

$len[i]$：$len[0]=freq[0],\ len[i]=len[i-1]+freq[i](i\gt 0)\ $($i$種類目までの文字を使った時の全体の文字列の長さ)

$i$：文字の数が$0$ではない文字の種類。全部で$n$種類とする。($0\le i \lt n$)

$j$：同じ文字が隣り合っている箇所の数(0から全ての文字を使った時の長さ-1が最大値)

$k$：同じ種類の文字を分割する数($1\le k\le freq[i+1]$)

$l$：$k$分割した文字列を同じ文字が隣り合っている箇所に入れる数($0\le l\le k,\ $$l\le j$)

初期値：$dp[0][freq[0]-1]=1$

求める解：$dp[n-1][0]$

${}_{freq[i+1]-1}\mathrm{C}_{k-1}$：長さが$freq[i+1]$の同じ文字からなる文字列を$k$分割した時の組み合わせの数

${}_{j}\mathrm{C}_{l}$：同じ文字が隣り合っている箇所$j$個のうち、$l$箇所に文字列を入れる場所の組み合わせの数

${}_{len[i]+1-j}\mathrm{C}_{k-l}$：同じ文字が隣り合っていない箇所$len[i]+1-j$個のうち、$k-l$個の文字列を入れる場所の組み合わせの数

明示していない条件として、$j$個の同じ文字が隣り合っている箇所に$l$個の分割した文字列を入れるので、$l\le j$でなければならない、$len[i]+1-j$個の同じ文字が隣り合っていない箇所に$k-l$個の分割した文字列を入れるので、$k-l\le len[i]+1-j$でなければならない、があります。

$i,j,k,l$のループで、$O(n\cdot len[n-1]\cdot 10\cdot 10)$です。

考察

「長さが$freq[i+1]$の同じ文字からなる文字列を$k$分割した時の組み合わせの数」ですが、分割したときに0個になるとだめなので、先に分割数分引いて残ったもの($freq[i+1]-k$)を0個も許して$k$分割すると考えます。0個も許して$k$分割するのは、$k-1$個の仕切りを加えて並べ替えを考えることで計算できます。つまり、${}_{freq[i+1]-k+k-1}\mathrm{C}_{k-1}$です。これは、$k$個の区別された箱に$freq[i+1]-k$個の区別できない球を入れる重複組み合わせ${}_{k}\mathrm{H}_{freq[i+1]-k}$と同じになります。

問題が複雑すぎて、詳しく解説するのがどんどん難しくなってきています。わかりにくいところを指摘していただければ、修正を加えたいと思います。