2022-03-21 ABC244 E - King Bombee を解いた
ABC244: AtCoder Beginner Contest 244 E - King Bombee を解いた。
問題: https://atcoder.jp/contests/abc244/tasks/abc244_e
本番では通せなかった。一晩明けて見たら素朴な DP だった。
まず偶数回の条件を無視して考える。移動回数ごとの状態で整理すると頂点ごとに到達できる場合の数を持てば十分だ。 dp[i][j] := (移動回数 i 回目のときに頂点 j に到達できる場合の数) 。遷移は i から i + 1 に移動するだけなので毎回生成するなら不要になる。 dp[K][T] が求めたい場合の数になる。
次に偶数回の条件を踏まえて考える。遷移先の頂点が X かを判定して偶奇を持てば良い。 dp[i][j][k] := (移動回数 i 回目のときに頂点 j に到達できる場合の数のうち k = 0 なら X に偶数回訪問・ k = 1 なら奇数回訪問) 。 dp[K][T][0] が求めたい場合の数になる。
提出: https://atcoder.jp/contests/abc244/submissions/30320156 解説: https://atcoder.jp/contests/abc244/editorial
子どもふたりを連れて自転車ですこし離れた公園へ行った。
今日のコミット。