はまやんはまやんはまやん

hamayanhamayan's blog

PDCAパス [yukicoder No.762]

https://yukicoder.me/problems/no/762

解法

https://yukicoder.me/submissions/307975

DPで解く。
dp[cu][t] := 頂点cuで終わり、PDCAのt番目まで正しく来ている組み合わせ
 

rep(cu, 0, N) if (S[cu] == T[0]) dp[cu][0] = 1;

これでdp[cu][0]の場合、Pの位置まで正しく来ているかカウント
 

rep(t, 1, 4) rep(cu, 0, N) {
    if (S[cu] == T[t]) fore(to, E[cu]) if (S[to] == T[t - 1]) dp[cu][t] += dp[to][t - 1];
}

これでdp[to][t-1]からdp[cu][t]への遷移で組み合わせ数をカウントする。
あとは、dp[cu][3]の総和が答え。

int N, M; string S;
vector<int> E[101010];
mint dp[101010][4];
string T = "PDCA";
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S;
    rep(i, 0, M) {
        int u, v; cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    rep(cu, 0, N) if (S[cu] == T[0]) dp[cu][0] = 1;

    rep(t, 1, 4) rep(cu, 0, N) {
        if (S[cu] == T[t]) fore(to, E[cu]) if (S[to] == T[t - 1]) dp[cu][t] += dp[to][t - 1];
    }

    mint ans = 0;
    rep(cu, 0, N) ans += dp[cu][3];
    cout << ans << endl;
}