ARC081 F - Flip and Rectangles
問題
h*wのマス目があり、各マスの色は黒か白である
「ある行[列]を選び、その行[列]の全てのマスの色を反転する」という操作を任意の回数行える
黒いマスのみを内側に含む長方形の面積の最大値を求めよ
2 <= h, w <= 2000
解法
タテかヨコの長さが1の長方形は明らかに自由に選べる
そうでない場合は？
2*2マスの正方形のうち黒マスを偶数個含むようなものは、操作によって4マスとも黒マスにすることができる
そういう正方形のみからなる任意の長方形も全部黒マスにできる (具体的には解説pdfの通り)
逆に奇数個含むような正方形はどう操作をしても無理
よって後者の正方形を内側に含まないような長方形のうち面積最大のものを求めればいい
これは蟻本p298のヒストグラムの最大長方形をスタックで求めるやつとほぼ同じようにできる
蟻本のやつ一回読んで理解できなくて投げたのは覚えてた
そろそろ上級編も読んだ方がいいかも・・
int h, w, ng[2020][2020], x[2020], res; string s[2020]; signed main() { cin >> h >> w; res = max(h,w); rep(i,h) cin >> s[i]; rep(i,h) { rep(j,w-1) { if (i && !(s[i-1][j]^s[i-1][j+1]^s[i][j]^s[i][j+1])) x[j]++; else x[j] = 1; } stack<int> s; rep(r,w) { while (!s.empty() && x[s.top()]>=x[r]) { int t = s.top(); s.pop(); int l = (s.empty() ? -1 : s.top()); chmax(res, x[t]*(r-l)); } s.push(r); } } cout << res << endl; }
