ABC171-F : Strivoreの解き方が少し想定解法と違ったので書き残しておく

想定解法と少し考え方が違ったので、私の解法を書いとこうかと思います。

注意：備忘録のようなものなので、少し解説としては雑です。ご了承ください。

まず、「好きな英小文字 $1$ 文字を好きな位置に挿入する」という操作を文字列 $S$ にちょうど $K$ 回繰り返してできる文字列は何通りあるでしょう？という問題は、 $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列はいくつあるでしょう？という問題に帰着させることができる。

ここで、 $S$ の頭 $i$ 文字を部分文字列(連続とは限らない)として含むかつ、頭 $\left( i+1\right)$ 文字は部分文字列として含まない $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の集合を $A_{i}$ とし、その要素数を $f\left( i\right)$ とする。 $\left( 0\leq i\leq \left| S\right| -1\right)$

また、便宜上 $S$ を部分文字列として含む $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の集合を $A_{\left| S\right| }$ とし、その要素数を $f\left( \left| S\right| \right)$ とすると、式 $\sum ^{\left| S\right|}_{i=0}f\left( i\right) =26^{ K+\left| S\right| }$ が成り立つ。なぜなら、任意のある $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列において、 $A_{0},A_{1},\ldots ,A_{\left| S\right|}$ のいずれか1つのみに必ず属すからだ。

出力する解は $f\left( \left| S\right| \right)$ であるが、私は直接求めるのではなく、上記の式を変形し、 $f\left( \left| S\right| \right)=26^{K+\left| S\right|}-\sum ^{\left| S\right|-1}_{i=0}f\left( i\right)$ としてから求めた。 $0\leq i\leq \left| S\right| -1$ において、 $f\left( i\right)$ は次のようなイメージで求めた。(図中のS_kを $S$ の $k$ 文字目とする)

f:id:regichan:20200622022835p:plain 上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列は全て $A_{i}$ に属し、逆に $A_{i}$ に属す文字列は全て上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列となるのは明確である。まず、 $S_{1},S_{2},\ldots ,S_{i}$ の配置パターン数は ${}_{K+\left| S\right|} C_{i}$ である。次に、ある配置パターンにおいてその他の文字を配置するパターン数は $25^{K+\left| S\right|-i}$ である。 $S_{1},S_{2},\ldots ,S_{i}$ の配置パターンが異なる場合、文字列がダブることはないため、上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の数すなわち $f\left( i\right)$ は、 ${}_{K+\left| S\right|} C_{i}\times 25^{K+\left| S\right|-i}$ となる。下処理を $O\left( K+\left| S\right|\right)$ で行うことで各iにおける $f\left( i\right)$ を定数時間で求めることができるため、全体として $O\left( K+\left| S\right|\right)$ で解くことができる。