読者です 読者をやめる 読者になる 読者になる

yukicoder No.307 最近色塗る問題多くない? の計算量

問題解説

唐突に解説を書きたくなったのでブログを生やしました。
嘘解法かと思って投げたのが想定解だった。

解説

writer解説
http://yukicoder.me/problems/769/editorial

想定解が計算量的になんとかなることの説明をします。

あるマスが{(H+W)}回色が変わると全てのマスが同じ色になります。(コドフェス2015リレーHっぽい)

よって、クエリで塗り替えられたマスの数の和が{HW(H+W)}になると、鳩ノ巣原理より、あるマスは{H+W}回以上色が変わるので、全てのマスが同じ色になっているはずです。

計算量は幅優先探索でマスの色を変える回数に比例するのと、クエリを読む分を合わせて{O(Q+HW(H+W))}になります。