【競プロ典型90問】008の解説（python）

概要

競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。

※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）

問題008-AtCounter

問題概要

文字列Sから任意の文字を順番を変えずに取り出したときに、"atcoder"(以下、文字列Tとします。)となる個数を求める。

解き方

まず初めに、単純にSから"atcoder"の文字をそれぞれ検索する方法が考えられますが、
この考えでは、文字列の長さNの検索を7回（Tの長さ分）行うため、$N^7$となりTLEになってしまいます。

そこで今回は、DP（動的計画法）を用います。
dp[i][j]を、Sのi文字目までを用いた時、Tのj文字目までを作る通りの数と定義します。
そうすると、
１. $S[i] = T[j]$の時（Sのi文字目とTのj文字目が等しい時）

$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$

※Sのi文字目を使ってTのj文字にする時と、Sのi文字を使わずにj文字目まで作った時の和です。

２. $S[i] ≠ T[j]$の時（Sのi文字目とTのj文字目が等しくない時）

$dp[i][j] = dp[i-1][j]$

※Sのi-1文字目までを使ってTのj文字を作る通り数と同じです。

の２つの漸化式が求められます。
また、j=0の時は、文字を取り出さない方法、すなわち１通りとできるので、

$dp[i][0] = 1$

i=0の時（かつj≠0）の時は、Sを１文字も使わず、Tのj文字まで作ることは出来ないため、

$dp[0][j] = 0$

と考えられます。ここまで求められると、i, jを小さい順から計算することで、
全てのi, jに対してdpを求めることができ、dp[N][7]が答えとなります。

引用元：競プロ典型90問 Github

実装

answer.py

# 入力の受け取り

N = int(input())
S = input()

# 今回はatcoderをTとする
T = "atcoder"

# 余りのための変数
mod = 10**9+7

#0文字からN文字まで考えるので、"+1個"配列を定義
dp = [[0]*(len(T)+1) for _ in range(N+1)]

# j=0の時、全て1を代入
for i in range(N+1):
  dp[i][0] = 1

# S[i]がT[j]に等しいかで場合分け
# dpのiとS[i]で示すiが1ズレている点に注意（jも同様）
# 答えをmodで割った余りを格納
for i in range(N):
  for j in range(len(T)):
    if S[i] == T[j]:
      dp[i+1][j+1] = dp[i][j] + dp[i][j+1]
      dp[i+1][j+1] %= mod
    else:
      dp[i+1][j+1] = dp[i][j+1]
      dp[i+1][j+1] %= mod

# N文字まで使って、Tになる時の通り数を出力
print(dp[N][len(T)])

最後に

問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）

ここまでお読みいただきありがとうございました。