ABC211_C - chokudai、雑にまとめる

解説を読んだけど、自分でかみ砕いた解説を出来たほうが良いなと思うので、備忘録的に多少雑でもまとめます。

文字列Sが与えられます。この中から8文字を選び、下線を引きます。選んだ文字が左から順に c, h, o, k, u, d, a, i となるような方法は何通りありますか？

ただし、答えが非常に大きくなる可能性があるため、(10⁹ + 7)で割った余りを出力してください。

#### 制約####

・8<=|S|<=10⁵

・Sは英小文字からなる

入力例 1

chchokudai

出力例 1

3

chchokudai
chchokudai
chchokudai
上の $3$ つが条件を満たします。

chchokudai
は、条件を満たさないことに注意してください。

らしい。

各文字について、後列でのchokudaiの作り方がどれ程あるのか調べれば行けそうと思ったけど、とても時間がかかりそう。

目標となる文字列の長さはchokudaiということで8文字なのでO(|S|×8)=O(|S|)だから、与えられた文字列について、chokudaiと比べあいっこするのかなーという感じ。

dp(動的計画法)を用いれば、dp[i][j]=「sのi文字目までを使ってchokudaiのj文字目にする方法」にできる。

jが0の時は、(Sのi文字目までを使って,長さ0の文字列を作る方法)になるので１

iが0の時は、(Sの0文字目までを使って,長さjの文字列を作る方法)になるので、0

初期値を0にして、for i in range(|S|)とかでdp[i][0]=1にしてあげればこれはいけそう。

1≤i≤|S|,1≤j≤8のときのdp[i][j]は

Sのi文字目とchokudaiのj文字目

・違うとき

・同じとき

が考えられるので、それぞれの場合について考えてみる。

まず違うとき、特にdpを更新する必要はないのでdp[i][j]=dp[i-1][j]になる。

次に同じとき、これも二通りの選択がある

Sのi文字目を

・使うとき

・使わないとき

使わないときは、特にdpを更新する必要はないのでdp[i][j]=dp[i-1][j]になる。

使うときは、Sのi-1文字目を使って、chokudaiのj-1文字目までを作る方法に等しいので、dp[i][j]=dp[i-1][j-1]

sのi文字目とchokudaiのj文字目が一緒でも、結局はsのi-1文字目を使ってchokudaiのj-1文字目までを作る方法に、新しい部分文字列を作る方法を足すしかないということ。

例えばs=ccchooo,text=choとすると

dp[3][1]=3(sの最初の3文字までを使ってtextの1文字目までに対応させるのは、c,c,cの3通り)

dp[4][2]=3(sの最初の4文字目までを使ってtextの2文字目までに対応させるのは、ch,ch,chの3通り)

みたいな感じ

したがって、同じときはdp[i][j]=dp[i-1][j]+dp[i-1][j-1]になる

以下、コード

S=input()
text="chokudai"
t=len(text)
s=len(S)
mod=10**9+7
dp=[[0]*(t+1) for _ in range(s+1)]
for i in range(s+1):
    dp[i][0]=1
for i in range(1,s+1):
    for j in range(1,t+1):
        if S[i-1]==text[j-1]:
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

↓提出コード

atcoder.jp