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

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

競プロ典型 90 問 008 - AtCounter(★4)

これまたすごく典型的な 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" としています。

f:id:drken1215:20220401161526p:plain

 

コード

計算量は "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)])

 

類題情報

状態遷移を意識する系の DP の類題たち!

drken1215.hatenablog.com

またその中でも特に、今回のような部分文字列に関する問題たち!

drken1215.hatenablog.com