AtCoder-ABC211 C - chokudai 【Python解答例】

AtCoder Beginner Contest211のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 211 - AtCoder

AtCoder Beginner Contest211 C - chokudai

C - chokudai

問題文

文字列 S が与えられます。
このうち 8 文字を選び下線を引き、下線を引いた文字が左から順に c , h , o , k , u , d , a , i となるようにする方法は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、(109+7) で割った余りを出力してください。

制約

・8≤|S|≤10^5
・S は英小文字からなる

解答例

S = input()

tar = "chokudai"

mod = 10**9 + 7

dp = [[0 for _ in range(len(tar)+1)] for _ in range(len(S)+1)]

for i in range(len(S)+1):
    dp[i][0] = 1

for i in range(len(S)):
    for j in range(len(tar)):
        if S[i] != tar[j]:
            dp[i+1][j+1] = dp[i][j+1]
        if S[i] == tar[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i][j]) % mod

print(dp[len(S)][8])

解説

動的計画法で答えを求めます。

dp[i][j]：Sのi番目の文字まででtar = "chokudai"のj文字目までをつくる組み合わせの数とおきます。

初期条件としてj = 0のときはd[i][0] =1とします。
また、i = 0ときはchokudaiから選択しようがないのでdp[0][j] =0とします。

この初期条件でiとjの2重ループでdpを更新していきます。

S[i] != tar[j]のとき、場合の数は増えることがありませんのでdp[i+1][j+1] = dp[i][j+1]としました。
S[i] = tar[j]のときは、Sのi番目の文字を使用しない場合は上記と同じでdp[i][j+1]通りです。
使用する場合は、Sがi-1番目の文字まででtarのj-1番目の文字をつくる組み合わせの数と同じdp[i][j]なのでこの２つの値を足し合わせます。

このようにdpを更新していき、最後にdp[len(S)][8]を出力すればＯＫでした。

ABC211の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com