ABC212 E Safety Journey
$ dp_{i, j} := $ i日目に都市$ jにいるような場合の数 としてDPをしていくことを考える. このDPは次に向かう頂点$ kをすべて試し, 条件を満たす$ jについて試すことで$ dp_{i + 1, k} = dp_{i + 1, k} + dp_{i, j}と遷移することができるが, 計算量が$ O(N^2K)となって間に合わない. ここで, $ Mの制約に注目すると, 使えない辺の本数は圧倒的に少ないということがわかる. 余事象を考えると, 次のようにこのDPを高速化することができる. まず, $ dp_{i, j}について, すべての$ jを試し, その総和を$ Sとおく. すると, $ dp_{i + 1, k}について, $ (j, k)が使えない辺となるような$ jについての$ dp_{i, j}の総和を$ Tとおくと, $ dp_{i + 1, k} = S - Tと遷移できる.
このような遷移の計算量を解析してみると, $ O(K(N + M))となり, これは十分高速である. よってこの問題を適切なDPの高速化により解くことができた.