連結DP 造語なのだが、連結性を状態として持つDP フロンティア法とかとも言う 問題 TDPC マス目 解説1 解説2 解説3 yukicoder No.541 3 x N グリッド上のサイクルの個数 解説1 解説2 解説3 yukicoder No.569 3 x N グリッドのパスの数 解説 ICPC模擬国内予選…

挿入DP 順列などに挿入することで遷移を進めていくDP 問題 HR Permutation Happiness SRM694 Div2 Hard UpDownNess 解説 CSA Restricted Permutations TDPC 文字列 解説1 解説2 解説3 CF429 On the Bench yukicoder No.93 ペガサス 解説1 解説2 http://kmjp.…

UnionFind, DSU 連結成分を管理するデータ構造 (解説) AtCoder Libraryで実装がある 最小全域木の構成でも使われる 連結時に成分に入っている情報を併合することもある(要素数とか) incremental(併合はできるが、分離はできない) (発展だが)永続UnionFindも…