atcoder.jp 各連結成分のサイズの最大値がちょうどという条件なので、最大値が以下の場合の数から最大値が以下の場合の数を引くことを考える。 を「サイズ以下の連結成分の集合で、頂点数が個、辺の数が本であるときの場合の数」とする。これに個の残りの頂…

atcoder.jp よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマ…

atcoder.jp 400点にしては難しいと感じた問題だった。 まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 について全探索するこ…