競プロ典型 008

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

文字列の中の位置とatcoderのどこまで一致したかを状態にして、その状態がいくつあるかをDPで求めます。

// AtCounter
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: u64 = 10u64.pow(9) + 7;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn read_input() -> String {
    let _N: usize = read();
    let S: String = read();
    S
}

fn convert(c: char) -> usize {
    match c {
        'a' => 0,
        't' => 1,
        'c' => 2,
        'o' => 3,
        'd' => 4,
        'e' => 5,
        'r' => 6,
        _   => 7
    }
}

type DP = [u64; 8];

fn initialize_dp() -> DP {
    let mut dp: DP = [0; 8];
    dp[0] = 1;
    dp
}

fn update_dp(n: usize, dp: DP) -> DP {
    if n == 7 {
        return dp
    }
    
    let mut new_dp: DP = [0; 8];
    
    for i in 0..8 {
        if i == n {
            new_dp[i+1] = (new_dp[i+1] + dp[i]) % D
        }
        new_dp[i] = (new_dp[i] + dp[i]) % D
    }
    new_dp
}

fn F(S: String) -> u64 {
    let N = S.len();
    let v: Vec<usize> = S.chars().map(|c| convert(c)).collect();
    
    let mut dp = initialize_dp();
    for i in 0..N {
        dp = update_dp(v[i], dp)
    }
    dp[7]
}

fn main() {
    let S = read_input();
    println!("{}", F(S))
}