ABC171 - F - Strivore(自分用)
概要
ある小文字アルファベットから構成される文字列Sが与えられる。これにK文字の任意の小文字を任意の位置にするとき、何通りの文字列が作れるのだろうか？
制約：1 <= |S|, K <= 10^6
今回は自分用をメインに書いてるためかなり雑。わかりづらいかもしれない。
考え方
1. いい感じに重複しない文字列を生成する操作列が何通りあるのかを考える。
2. ある文字列の間に1文字ずつ文字を挿入することを考える。ある区間では26通り、他では25通り挿入できる。
3. しかしこれは嘘解法。S="ab"から2つ挿入してababにする操作列は2通り以上あり、ダブルカウントしてしまう。
4. 結局正しい解法はなんでも可能な部分を固定して計算し、それを足し合わせること。
考察
言いたいことがすべてここにある。(至言)
drken1215.hatenablog.com
以下個人的なメモ
解法1
最後尾のなんでもOKの26通り部以外の文字では、それぞれS[i]に割り当てられている区間はアルファベット小文字26文字のうちS[i]を使ってはいけないというルール。
なぜこのルールで重複もれなく数え上げられるのだろうか。
最終的な文字列Xを考えるとき、Xのうちの部分文字列Sが何通りも取れる場合がある。(X="abab"に対するS="ab"、X[0]~S[0], X[1]~S[1]やX[0]~S[0], X[4]~S[1]などの数通りの候補がある)このような場合はまさに異なる操作列でも同じ結果にたどり着くというもの。
これらを重複なく、現れる文字列のパターン数を数え上げるには部分列DPでの似たような感じでS[i]としてありうる「最初」or「最後」のX[j]をS[i]から来たとして、残りはすべて挿入されたものとして考えると考察がしやすい。例えば、S="ab", X="abab"の場合、Xのうち、条件を満たす最初の文字がSから来てるとすると、S+"ab"＝=XとSの最後に"ab"をくっつけた、ということになる。
けんちょんさんの記事では、最後に現れたXの中でSとなる部分文字列をSから来ていて、他のアルファベットは挿入した形としている。もちろんこれは一般性を保っている。
ゆえに、解説PDFのようなあるアルファベット以外使用禁止なので25通りになるのような論理となる。
S="ab"の場合、T="aacacbc"を作るのならば、T="aacacbc"の形で他の5文字を挿入したことになる。
解法1のソース：
Submission #15775871 - AtCoder Beginner Contest 171
解法2
あとでかく
解法3
あとでかく
最後に
けんちょんさんは偉大
