競プロ典型90問 008 AtCounter

(問題ページ) 競プロ典型90問 008 AtCounter
https://atcoder.jp/contests/typical90/tasks/typical90_h

---

文字列atcoderの中の文字を選ぶ時の場合の数を、dp["文字"]というふうに連想配列で表すことにします。
例：文字"c"を選ぶ場合の数は、dp["c"]

(今回、文字列atcoderは、すべて異なる文字が使われているため、変数dpは連想配列にしました。)

考え方

入力例1の文字列attcordeerを、左から順に走査していきます。

走査した文字が"a"だったとき、そこから文字列atcoderが始まるため、"a"を選ぶ場合の数を+1します。
dp["a"]++

次に、
たとえば4文字目の文字"c"を選ぶ場合の数は、その時点で文字"t"まで選んだ場合の数をプラスすればいいことになります。
言い換えると、「(3文字目までで)"at"まで文字列を作成した場合の数」が、次(4文字目)に"c"を選ぶ場合の数になります。
変数dpは、走査の間、使いまわすため、場合の数を足し合わしていくことになります
dp["c"] += dp["t"]

同様に考えて、
文字"t"を選ぶときは、「その時点で"a"まで選んだ場合の数」をプラスする。
文字"o"を選ぶときは、「その時点で"c"まで選んだ場合の数」をプラスする。
文字"d"を選ぶときは、「その時点で"o"まで選んだ場合の数」をプラスする。
文字"e"を選ぶときは、「その時点で"d"まで選んだ場合の数」をプラスする。
文字"r"を選ぶときは、「その時点で"e"まで選んだ場合の数」をプラスする。
となります。

code

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
#include <functional>
#include <unordered_map>


int main() {
    int N;
    string S;
    cin >> N >> S;
    int mod = 1000000000 + 7;

    // 文字列atcoder の各文字の取りうる組合せ
    unordered_map<string, long long> dp;

    for (int i = 0; i < N; i++) {
        if (S[i] == 'a') {
            dp["a"]++;
            dp["a"] %= mod;
        } else if (S[i] == 't') {
            dp["t"] += dp["a"];
            dp["t"] %= mod;
        } else if (S[i] == 'c') {
            dp["c"] += dp["t"];
            dp["c"] %= mod;
        } else if (S[i] == 'o') {
            dp["o"] += dp["c"];
            dp["o"] %= mod;
        } else if (S[i] == 'd') {
            dp["d"] += dp["o"];
            dp["d"] %= mod;
        } else if (S[i] == 'e') {
            dp["e"] += dp["d"];
            dp["e"] %= mod;
        } else if (S[i] == 'r') {
            dp["r"] += dp["e"];
            dp["r"] %= mod;
        }
    }
    printf("%lld\n", dp["r"]);
}