けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

包除原理: DP

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

EDPC Y - Grid 2

座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…