in-place DP:シフトすることで更新箇所を減らす
AtCoder
AtCoder525点
ABC-F
青色diff
NoviSteps2D
数珠
座標圧縮
グラフの辺数削減テク:いくつかの頂点をひとまとめに縮約する
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
DP
シーケンシャルDP
グラフの経路数の数え上げ
in-place DP
in-place DP:シフトすることで更新箇所を減らす
制約条件:辺数=K
が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフがある。 辺 () は、頂点 から頂点 を結ぶ ( は 0 とする) 辺 () は、頂点 から頂点 を結ぶ このグラフ上の、頂点 0 を始点と…
