atcoder.jp2乗の木dp なのでdpのサイズは気にしなくていい切り離したものは条件を満たしていないといけないが、今見ている連結成分は後々マージされるためその限りではない Submission #4131219 - AISing Programming Contest 2019 / エイシング プログラミ…

E - Weights on Vertices and Edgesコストが大きいものから辺を消していきたい しかし実現困難なため逆の操作を行うコストが小さいものから辺を繋いでいくある辺を繋いだ時にその辺が成り立つ場合、集合内の辺はすべて成り立つこれはunionfindで頂点につなが…

C - 部門分けo(n ^ 3)で部分集合が列挙できる いくつかの集合に分けるため、それらの評価値を独立して考えたい 部分問題として考えるには dp[m] := 全体の集合がmとした時の問いの答えとすればいい 遷移はdp[m] = dp[s] + dp[m-s] - 二つの間の信頼値の合計…

D - Double Landscape 解法まず縦横に同じ数があってはいけないabをソートするそのうえで、大きい数から置ける範囲を考えていくと 前回の範囲を含む長方形となるため、その中から一つ自由に選べる（今までに置いた数だけ 置ける場所は引かれる） ただし、aか…