H - Grid Eraser Editorial by idsigma


\(H=1\) のときは \(W\)\(W=1\) のときは \(H\) です。

\(H,W \geq 2\) のときを考えます。ある行を消去したことで、消去できた列が消去できなくなることはありませんし、逆も同様です。よって、操作ができる行や列を探して、できるなら操作を行うということを繰り返せば \(H=1\) または \(W=1\) の場合に帰着されます。

このシミュレーションを愚直に行うと 計算量が \(O((H+W)^3)\) となり間に合いません。高速化するには、各行と各列の黒(白)マスの数と、現在の行数/列数を管理します。そうすると、各行/列が消去できるかの判定が \(O(1)\) で可能です。消去することにした場合、黒/白マスの数の変更を反映する必要がありますが、この作業のは全体でマス目の数である \(O(HW)\) しかかかりません。操作回数の上限は \(H+W\) 回 ですから、毎回すべての行と列が消去可能かをチェックして、消去できるなら更新を行う、というシミュレーションが \(O((H+W)^2)\) で可能になります、

posted:
last update: