競プロ典型90問：008 - AtCounter（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_h

挑戦結果

• 結果：解けた
• 時間：30分ぐらい

考えたこと

• DPっぽいことは最初から感じた
• 遷移の条件に苦労した

公式解説

https://twitter.com/e869120/status/1379927227739987972?s=20

解説を読んだふりかえり

• DPの作り方は解説と同じで良かった。少しDPに慣れてきたか。
• ただ、時間もかかったし、理解度がまだ足りてない感じはする。

ソース

N = int(input())
S = input()
MOD = 10**9 + 7
# 先頭に足して1-originにする。末尾も範囲チェックを楽にする都合で追加
ATCODER = "_atcoder_"
S = "@" + S + "@"

# DPテーブルは大きめに確保
# dp[i][j]のとき、
# Sのi文字目まで使用していて、"atcoder"のj文字目までカバーしているパターン数
dp = [[0] * (len(ATCODER)+10) for _ in range(N+10)]
# Sを0文字目まで使っていて、"atcoder"の0文字目までカバーしているのが1パターン。
dp[0][0] = 1

# 配るDP
for i in range(N+1):
    for j in range(7+1):
        # 遷移①：使える文字数が増えても、既存パターン数はOK
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        # 遷移②：使える文字が増えて、atcoderの次の文字とマッチする場合
        if ATCODER[j+1] == S[i+1]:
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD

print(dp[N][7])