[AtCoder] HHKB プログラミングコンテスト 2020 E – Lamps

問題

方針

照らされるマスについて

散らかっていないマス \( (i, j) \)に照明を置いたとき、水平方向を照らすマスの数を \( a(i, j) \) とし、垂直方向を照らすマスの数を \( b(i, j) \) とします。このとき、照らされるマスの合計は \( a(i, j) + b(i, j) – 1\) となります。これらは、Union-Find を使うことで求めることができます。つまり、マス \( (i, j)\) と連結なマスの個数が \( a(i, j) + b(i, j) – 1\) 個あるということです。

マス \( (i, j) \) は、\( Wi + j \) とすることで、\( 1 \) 次元配列として扱うことができます。

照明の置き方

散らかっていないマスの個数を \( n \) とします。マス \( (i, j) \) が照らされる照明の置き方は、マス \( (i, j)\) と連結なマスに \( 1 \) 個以上照明を置く場合の数とマス \( (i, j)\) と連結でないマスの照明の置き方の積なので、\( t_i = a(i, j) + b(i, j) – 1 \) として、

\[ (2^{t_i} – 1) 2^{n – t_i}\]

となります。したがって、全ての散らかっていないマスに対して、上記を求めて足し上げます。

コード