hitoare日記

たまに書きます

F - Strivore(AtCoder Beginner Contest 171)

問題リンク

atcoder.jp


問題概要

英小文字からなる文字列\(S\)と自然数\(K\)が与えられる。

\(S\)に「好きな位置に好きな英小文字を1つ挿入する」という操作をちょうど\(K\)回繰り返して得られる文字列の総数は何通りか。

解法

\(S\)の文字数を\(N\)とおく。

求めるものは、「\((N+K)\)文字の文字列で、\(S\)を(連続とは限らない)部分列に持つものの総数」である。

これは次のように言い換えられる。

  • a~zの文字が書かれた26面体のサイコロがある。Sの先頭から見て、現在見ている文字と同じ文字が出たらそれを書いて次の文字に進む、という作業を\((N+K)\)回繰り返す(\(S\)が完成してもサイコロは振り続ける)。目の出方\(26^{N+K}\)通りのうち、\(S\)が完成するのは何通りか。

\(N \leqq i \leqq N+K\)とし、ちょうど\(i\)回目で\(S\)が完成する場合を考えると、

\(1...(i-1)\)回目ではちょうど\(N-1\)回当たりの目(見ている文字と一致する目)、\(i-N\)回外れの目が出て、

\(i\)回目では\(S\)の最後の文字が出て、

\((i+1)...(N+K)\)回目では任意の目が出ている。

よってこの場合の総数は \( {}_{i-1} C_{N-1} \times (26-1)^{i-N} \times 26^{N+K-i} \) 通りになる。

これを\(i\)を\(N\)から\((N+K)\)まで動かして足せば答えが出る。

また、「当たりの目がN回以上出る組み合わせの総数」と考えて

\(\sum_{i=N}^{N+K} ({}_{N+K} C_{i} \times (26-1)^{N+K-i} )\)としても答えが得られる。

提出 

https://atcoder.jp/contests/abc171/submissions/14552574

感想

昨日のAGCでも文字列の数え上げが2つ出たけど、どれも違う解法で良かった。