ABC234F Reordering - geam1113’s diary

解説AC

問題へのリンク
 公式解説

単純に部分列を得るだけなら部分列DPなどが考えられますが、今回はすべての並び替えを得る必要があるので適用できません。
重複を含む並び替えの計算方法から考えてみます。

$a,b,c,\cdots ,z$ の選んだ個数をそれぞれ $A,B,C,\cdots , Z$ とします。この時の並び替えの方法は、

$\frac{(A+B+C+\cdots +Z)!}{A!\cdot B! \cdot C! \cdot\ \cdots \ \cdot Z!}$

です。

よって、各文字を何個選んだかという情報があれば、並び替えが何通りあるか得ることができます。
そこで、それぞれ何個選ぶかをDFSで全探索してみましたが、到底間に合いませんでした。

ここからは公式解説の方法に自分の補足を加えながら書いてみます。

実は、どの文字を何個選んだかという情報は不要で、合計で何個選んだかさえ分かれば、その時に選んだ文字数に対する文字列の並び方の総数を計算できるということでした。

具体例として、aが3個、bが3個ある場合に、a,bから合計4個選んだ時の並び替えの総数から、その後cから3個選んだ時の並び替えの総数への遷移を考えます。

aを3個、bを1個選んでいた場合
$\frac{4!}{3!1!}$ が $\frac{7!}{3!1!3!}$ になります。
よって、
$\frac{4!}{3!1!}\times {}_7C_4 = \frac{7!}{3!1!3!}$ です。
aを2個、bを2個選んでいた場合
$\frac{4!}{2!2!}$ が $\frac{7!}{2!2!3!}$ になります。
よって、
$\frac{4!}{2!2!}\times {}_7C_4 = \frac{7!}{2!2!3!}$
aを1個、bを3個選んでいた場合
$\frac{4!}{1!3!}$ が $\frac{7!}{1!3!3!}$ になります。
よって、
$\frac{4!}{1!3!}\times {}_7C_4 = \frac{7!}{1!3!3!}$

以上から、
$(\frac{4!}{3!1!}+\frac{4!}{2!2!}+\frac{4!}{1!3!})\times {}_7C_4 = \frac{7!}{3!1!3!}+\frac{7!}{2!2!3!}+\frac{7!}{1!3!3!}$
となります。

ここで、dpを考えます。a,b,c,...を1番目,2番目,3番目,...とします。
$dp[i][j]:=i$ 番目までの文字を考えたとき、これまで選んだ文字の合計個数が $j$ の時の、並び替えによって得られる文字列の総数
と、定義します。

すると、

$dp[2][4]=\frac{4!}{3!1!}+\frac{4!}{2!2!}+\frac{4!}{1!3!}$
$dp[3][7]= \frac{7!}{3!1!3!}+\frac{7!}{2!2!3!}+\frac{7!}{1!3!3!}$

であることから、

$dp[3][7]=dp[2][4]\times {}_7C_4$

となって、bまでで文字を合計4個選んだ時の文字列の総数から、cまでで文字を合計7個選んだ時の文字列の総数を計算できました。

一般化すると、 $i-1$ 番目までで文字を合計 $k$ 個選んだ時の文字列の並び替えの総数から、 $i$ 番目で $j$ 個選んだときの文字列の並び替えの総数は、

$dp[i][j+k]\leftarrow dp[i-1][k]\times {}_{j+k}C_k$

と計算できます。

計算量についてです。
解説の実装部分は読まずに実装してみました。

    dp[0][0] = 1;
    ll sum = 0;
    rep(i,1,27) {
        rep(j,C[i-1]+1) {
            rep(k,sum+1) {
                dp[i][k+j] += dp[i-1][k]*cn.nCr(k+j,k);
            }
        }
        sum += C[i-1];
    }

こちらのdpの遷移部分の計算量ですが、jのループは、i番目の文字に対して毎回Sの文字数分回されるのではなく、
1〜26番目の文字全体を通して、合計でSの文字数分回されるので、ワーストの見積もりで26×5000×5000という計算量になるわけではなく、実際にはもっと少ない計算量になると理解しました。

提出コード