これまたすごく典型的な DP！！！
「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。

この問題の前提知識

ナップサック問題を解く DP が自力で書けること
1000000007 で割ったあまりを求めることに不自由がないこと

問題概要

長さ $N$ の文字列 $S$ が与えられます。

文字列 $S$ から何文字かを抜き出します。

抜き出し方は $2^{N}$ 通りありますが、そのうち抜き出した文字列をその順に並べると "atcoder" となるものが何通りあるかを求めてください。

ただし、1000000007 で割ったあまりで答えてください。

制約

$1 \le N \le 10^{5}$

$2^{N}$ 通りの全探索は DP で解けることが多い！

今回の問題のように、「 $2^{N}$ 通りの場合を考える」という問題では DP で解ける率がとても高いです！！！

かなり高い確率で次のような DP で解けます。

dp[i][(なんらかの状態)] ← $N$ 個のうち最初の $i$ 個についてのみ、「選ぶ」「選ばない」を決めたときに、(なんらかの状態) になるような場合の数

一例として、ナップサック問題も次のような DP で解けました。

dp[i][w] ← $N$ 個の品物のうち最初の $i$ 個について、選ぶか選ばないかを決めたときに、選んだ品物の重さが $w$ 以下となる場合についての、選んだ品物の価値の総和の最大値

今回の DP

今回は次のような DP で解けます。

dp[i][j] ← 文字列 $S$ の最初の $i$ 文字から何文字か抜き出してつなげる方法のうち、それが "atcoder" の最初の $j$ 文字まで一致するような方法の個数

遷移は次のように書けます (MOD をとる部分は省略)。文字列 $S$ の最初の $i$ 文字までについての解 (dp[i]) から、 $i+1$ 文字までについての解 (dp[i+1]) を更新します。このとき、S[i] を選ぶか選ばないかで場合分けします。

// S[i] を選ばない場合
dp[i+1][j] += dp[i][j];

// S[i] を選ぶ場合 (T = "atcoder" とする)
if (S[i] == T[j]) {
    dp[i+1][j+1] += dp[i][j];
}

また初期値は dp[0][0] = 1 です。

遷移の様子を例示すると、次のようになります。ただし簡単のため、"atcoder" ではなく、"atc" にしています。また $S$ = "aatctc" としています。

コード

計算量は "atcoder" の文字数を $M$ とすると $O(NM)$ です。実際は $M$ は定数とみなせるので $O(N)$ です。

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const string T = "atcoder";

// a に b を足して、MOD をとる関数
void add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int main() {
    int N;
    string S;
    cin >> N >> S;

    // DP テーブル
    vector<vector<int>> dp(N+1, vector<int>(T.size()+1, 0));

    // 初期条件
    dp[0][0] = 1;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= T.size(); ++j) {
            // S[i] を選ばない場合
            add(dp[i+1][j], dp[i][j]);

            // S[i] を選ぶ場合
            if (j < T.size() && S[i] == T[j]) {
                add(dp[i+1][j+1], dp[i][j]);
            }
        }
    }
    cout << dp[N][T.size()] << endl;
}

Python3

MOD = 1000000007
T = 'atcoder'

# a に b を足して MOD をとる関数
def add(a, b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

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

# DP テーブル
dp = [[0]*(len(T)+1) for _ in range(N+1)]

# 初期条件
dp[0][0] = 1

# ループ
for i in range(N):
    for j in range(len(T)+1):
        # S[i] を選ばない場合
        dp[i+1][j] = add(dp[i+1][j], dp[i][j])

        # S[i] を選ぶ場合
        if j < len(T) and S[i] == T[j]:
            dp[i+1][j+1] = add(dp[i+1][j+1], dp[i][j])

print(dp[N][len(T)])

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

この問題の前提知識

問題概要

制約

$2^{N}$ 通りの全探索は DP で解けることが多い！

今回の DP

コード

C++

Python3