アルゴリズム忘備録

競技プログラミングとかデータ分析とか

HHKB プログラミングコンテスト 2020 E - Lamps

atcoder.jp

 

よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマス目をカウントして行くと O(HW \max(H, W)) とかになってしまうが、一つ隣のマスを使うDPみたいなことをすることで O(HW)で数えられる。マス (i, j) における上下左右に散らかってない連続したマスの数を a_{i, j}、全体の散らかってないマスを totalとしたとき、そのマスは (2^{a_{i, j}} - 1) * 2^{total - a_{i, j}} 回カウントされる。これを行と列で総和を取れば良い。計算量は O(HW)