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

hamayanhamayan's blog

Safety Journey [AtCoder Beginner Contest 212 E]

https://atcoder.jp/contests/abc212/tasks/abc212_e

前提知識

解説

https://atcoder.jp/contests/abc212/submissions/24697855

難しくなってくる。今回の問題はまずDPが分かっていることは前提で、その上で高速化をしていく必要がある。

なぜDPが思いつくか

毎回難しい部分で、mod上での数え上げと制約からDPが思い浮かんでDPを考えていくと解けたと言う他ない。
解説などでDPで解きます。と書いてあっても、実際解いている過程でマジでそんな感じなんだと思う。
恐らく、今回のABCではtouristは全問そんな感じだったんだろう。

DPで解く

以下のようなDPで解いていく。

dp[day][lst] := day日間の旅が終了していて最後に都市lstにいるときの旅の組み合わせ数

これが解ければdp[K][1]が答えになることは分かるだろう。
愚直に計算しようとすると、dp[day][lst]について都市lstから移動可能な都市nxtへ
dp[day+1][nxt] += dp[day][lst]のような感じで遷移していく感じになる。
遷移回数がこれだと、状態がO(N2)で遷移がO(N)なのでO(N3)となり間に合わない。

制約をついて高速化する

今回の制約には実は弱い部分があって、Mの最大数が5000であることである。
ここが怪しい部分でここから高速化を導くことができる。

普通にDPの遷移をやろうと思うと、各都市から遷移可能な都市をすべて確認するような感じになるので、
各日で遷移数はO(N2)になる。これは間に合わない。
だが、遷移に「使われない辺」の遷移に着目してみると、これはM本の辺なのでO(M)で済む。
ここが重要な改善ポイント。

DP高速化へ

DP高速化の前段階として良く行われる、配るDPから貰うDPへの変換をしよう。
現状は配るDPとなっており、遷移元のdp[day][lst]を全探索して、遷移可能なdp[day+1][nxt]にその値を足しこんでいく。
逆にdp[day+1][nxt]を全探索して、遷移元dp[day][lst]を足しこんでいくような実装に変えてみよう。

dp[day+1][nxt] = sum{nxtから遷移可能なlst} dp[day][lst]

このような実装をやると貰うDPへの変換が完了する。
この遷移可能というのを遷移できないに変換すると、このような感じになる。

dp[day+1][nxt] = (dp[day][lst]の全部の組み合わせ) - sum{nxtから遷移不可能なlst} dp[day][lst]

逆を取って全体から引くような感じになる。
この全部の組み合わせはnxtのループに入る前に変数totとして計算しておく。
nxtから遷移不可能な先というのは、指定された辺と自分自身への辺の2種類があるので、その分を引く。
こうすると、遷移の回数は全部まとめると(ならしで)N+2M回になるので間に合う。

これで全体O(N(N+M))でAC.

int N, M, K;
vector<int> E[5050];
mint dp[5010][5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, M) {
        int U, V; cin >> U >> V;
        U--; V--;
        E[U].push_back(V);
        E[V].push_back(U);
    }
    
    dp[0][0] = 1;
    rep(day, 0, K) {
        mint tot = 0;
        rep(lst, 0, N) tot += dp[day][lst];
        rep(nxt, 0, N) {
            dp[day + 1][nxt] = tot - dp[day][nxt];
            fore(lst, E[nxt]) dp[day + 1][nxt] -= dp[day][lst];
        }
    }

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