AtCoder Beginner Contest 234 F 問題 Reordering

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$S$ から連続とは限らず1文字以上抜き出した後, 並び替えることでできる文字列はいくつか?

制約

$S$ は英小文字からなる文字列
$1 \leq |S| \leq 5000$

解法

$\mathcal{A}$ で英小文字全体の集合とし, $\alpha \in \mathcal{A}$ と文字列 $U$ に対して $\chi_\alpha(U)$ で $U$ に含まれる $c$ の数とする.

非空文字列 $T$ が作成可能であることの必要十分条件は,

任意の $\alpha \in \mathcal{A}$ に対して, $\chi_\alpha(T) \leq \chi_\alpha(S)$

である.

$\mathbb{N}^\mathcal{A}$ に対して, 和と順序, 重さを $\boldsymbol{i}=(i_\alpha), \boldsymbol{j}=(j_\alpha)$ に対して,

$\boldsymbol{i}+\boldsymbol{j}:=(i_\alpha+j_\alpha)$
$\boldsymbol{i} \leq \boldsymbol{j} :\iff \forall \alpha \in \mathcal{A}; i_\alpha \leq j_\alpha$
$|\boldsymbol{i}|:=\sum_{\alpha \in \mathcal{A}} i_\alpha$

と定義する.

すると, 問題は $\boldsymbol{k}:=(\chi_\alpha(S))$ として, $(\chi_\alpha(T)) \leq \boldsymbol{k}$ となる非空文字列の数 $E$ を求めることになる.

$\boldsymbol{i}=(\chi_\alpha(T))$ となる $T$ の個数を $M_\boldsymbol{i}$ と置くと,

$\displaystyle E=\sum_{\boldsymbol{0} \neq \boldsymbol{i} \leq \boldsymbol{k}} M_\boldsymbol{i}$

である.

$\boldsymbol{i}$ を固定し, $M_\boldsymbol{i}$ について考える. これは

$M_\boldsymbol{i}=\dfrac{|\boldsymbol{i}| !}{\prod_{\alpha \in \mathcal{A}} i_\alpha !}$

である.

$|\boldsymbol{i}|=n$ であるようなものをまとめると,

$\displaystyle \sum_{|\boldsymbol{i}|=n} M_\boldsymbol{i}=n! \sum_{|\boldsymbol{i}|=n} \dfrac{1}{\prod_{\alpha \in \mathcal{A}} i_\alpha !}$

であるが, これを多項式の係数とみなすと, 各 $\alpha \in \mathcal{A}$ に対して,

$\displaystyle P_\alpha(X):=\sum_{m=0}^{\chi_\alpha(S)} \dfrac{1}{m!} X^m$

とおくと,

$\displaystyle \sum_{|\boldsymbol{i}|=n} M_\boldsymbol{i}=n! \left(\left[X^n \right] \prod_{\alpha \in \mathcal{A}} P_\alpha \right)$

よって, 求めるべき正解は

$\displaystyle E=\sum_{n=1}^{|S|} \sum_{|\boldsymbol{i}|=n} M_\boldsymbol{i}=\sum_{n=1}^{|S|} n! \left(\left[X^n \right] \prod_{\alpha \in \mathcal{A}} P_\alpha \right)$