Strivore (ABC171F)

投稿者: | 2020年6月21日

頭の整理がてら、ABC171のF問題Strivoreの解説をしようと思います。

問題

「好きな英小文字1文字を好きな位置に挿入する」という操作を文字列SにちょうどK回繰り返してできる文字列は何通りあるでしょう?

制約

  • K <= 10^6
  • size(S) <= 10^6

考え方

  • 文字列Sに対してを1文字ずつ足してDPをするのは難しそう
  • 文字列Sに操作をK回行った文字列の長さはsize(S)+k文字である

操作後の文字列の長さをn= size(S)+kとします。

この 26^n 通りの文字列から求めたい文字列が何個あるか、と考えると問題を以下のように言い換えることができます

長さnの文字列のうち、文字列Sを部分列として含むものは何通りあるか?

これならDPできそうです。

実際、dp[i][j]を「長さiの文字列ででS1〜Sjまでを部分文字列として含む文字列の数」としたらDP可能です。

DP更新式は「Sj文字目の値を選ぶか、それ以外の値を選ぶか」で決まるため

となります。

本来ならsize(S)文字目以降を
dp[i+1][k] = dp[i][k] * 26;
とし、dp[n][k]とするのが正しいですが、サンプルコードのように、下記式のように和をとっても同じ値になります。

     \begin{equation*} \sum_{i=size(S)}^{n} dp[n][i] \end{equation*}

ただし、これではまだO(n^2)であり、TLEしてしまいます。

DPの表と更新式を見ると、これは二項係数であることが分かります。

↓二項定理

     \begin{equation*} \sum_{k=0}^n _{n}C_{k} \, x^k \, y^{n-k} = (x+y)^n \end{equation*}

よって、求める値は

     \begin{equation*} \sum_{i=size(S)}^n _{n}C_{i} \, 25^{n-k} \end{equation*}

となります。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です