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

hamayanhamayan's blog

King Bombee [AtCoder Beginner Contest 244 E]

競技プログラミング

https://atcoder.jp/contests/abc244/tasks/abc244_e

前提知識

解説

https://atcoder.jp/contests/abc244/submissions/30321733

まず前提としてDPが分かっていないとこの問題を解くことは難しい。
DPが未履修であれば、先に学習してこよう。
DPの入門問題としては向かない。

DP？

mod数え上げは意外と選択肢が無いし、数列の数え上げなのでDP感がすごい。
DPに乗せられるように情報を圧縮していくことを考えよう。

最初は
dp[i] := 数列A[i]まで確定している数列の組み合わせ
からスタート。

数列のA[i]まで確定しているときに次のA[i+1]を決めるには最後の要素が何かだけ分かっていればいい。
なので、状態として最後の要素を含める必要がある。
dp[i][lst] := 数列A[i]まで確定していて、最後の要素がlstである数列の組み合わせ

だが、これでは整数Xの出現回数が分からないので答えを導くことができない。
なので、整数Xの出現回数を含めるのだが、
dp[i][lst][cnt] := 数列A[i]まで確定していて、最後の要素がlstであり、Xがcnt回出現した数列の組み合わせ
としてしまうと状態数がO(KN2)となりちょっとメモリに載らない。
載らないし、計算量もアレなので、問題に即して偶数回出現しているかを保持することにしよう。

dp[i][lst][mod2] :=
数列A[i]まで確定していて、
最後の要素がlstであり、
Xが出現した回数を2で割ったあまりがmod2である
数列の組み合わせ

これがDPの定義になる。
あとはこれを実装する。

実装の注意点

状態のループで既にO(NK)なのであまり無茶はできない。
普通の更新の感じで
dp[i][lst][mod2]からdp[i+1][to][next_mod2]みたいな感じにtoを全探索するとO(N2 K)となって間に合わない。
lst -> toへは辺にあるものだけ実施すればいいのでtoを全探索するのではなく、lstから辺があるtoを全探索しよう。
すると、計算量はO(K(N+M))となって間に合う。

補足：O(K(N+M))？？

N+Mの部分が良く分からないと思うのだが、ならし計算量が混ざっている。
例えば rep(lst, 0, N) rep(to, 0, N)とするとこれはO(N2)である。
だが、rep(lst, 0, N) foreach(to, E[lst])とtoをlstから遷移可能なものにforeachで列挙するとO(N+M)となる。
O(N+M)ということはO(N)とO(M)で大きいほうが最終的な（支配的な？専門的な言い方が分からない）計算量となる。

rep(lst, 0, N) foreach(to, E[lst]) { // ここの計算 }のコメント部分が何回評価されるだろうかというのを
考えると、辺があると評価されるので2M回評価されることになる。
「ならし」で2M回評価されるので、処理全体で見るとO(M)ではあるのだが、foreachの評価回数を見るとN回なので、
ループ的にはO(N)で、ネスト内部の評価回数はO(M)となるので、O(N+M)

int N, M, K, S, T, X;
vector<int> E[2010];
mint dp[2010][2010][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K >> S >> T >> X;
    S--; T--; X--;

    rep(i, 0, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dp[0][S][0] = 1;
    rep(i, 0, K) rep(lst, 0, N) rep(mod2, 0, 2) {
        fore(to, E[lst]) {
            dp[i + 1][to][mod2 ^ (to == X)] += dp[i][lst][mod2];
        }
    }

    cout << dp[K][T][0] << endl;
}