ARC081-F Flip and Rectangles
解法
全部黒にできる長方形は、行の集合を選んで flip すると、必ず各列の色がすべて同じになる。 これは、操作をいくら行っても変わらない性質である。
この判定には本来毎回 かかるが、適切な前計算で高速にできる。
具体的には、隣接2列の組にだけ注目すると、すべての隣接2列で条件を満たしていれば全体でも条件を満たすことがわかるので、すべての隣接2列について前計算しておく。
ここで、判定に使う情報を条件に転換してやると、すべての隣接2列について、同じ長方形に含められない隣接2行の場所が列挙できる。
これを利用すると、左端を固定して右端を右に伸ばしていくとき、同じ長方形に含められない隣接2行を含まないような区間の、縦の長さの最大値を高速に求められればよいことがわかる。
どこまで右端を伸ばした時にある隣接2行が使えなくなるかをそれぞれ二分探索で求めて、列の順でソートしたあと、縦向きの区間とその長さを std::set で管理しながら移動していけばよい。
これで、この問題が で解けた。
定数倍が重めだが、枝刈りを適切にすると通る。
