misora192 https://blog.hatena.ne.jp/misora192/ mini notes https://mini-notes.hatenablog.com/ 問題：E - Safety Journey 解答：Submission #24919698 - AtCoder Beginner Contest 212 解法：DP。 dp[i][j]：i日目に都市jにいるときの場合の数とする。答えはdp[K][0]である。 Eを使える道の集合とする。 dp[i][j] = Σdp[i-1][k] ( (k, j) in E) = Σdp[i-1][k] (all k) - Σdp[i-1][k] ( (k, j) NOT in E) ここで、「all k」は各j間で使いまわし可能、「(k, j) NOT in E」は問題で与えられる辺の集合で全てのjを計算し… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmini-notes.hatenablog.com%2Fentry%2F2021%2F08%2F09%2F222457" title="ABC212 E - Safety Journey - mini notes" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-08-09 22:24:57 rich https://mini-notes.hatenablog.com/entry/2021/08/09/222457 1.0 100%