AtCoder ARC #081 : F - Flip and Rectangles

うーん。
https://beta.atcoder.jp/contests/arc081/tasks/arc081_d

問題

N*Mのグリッドが与えられる。
各セルは白黒のいずれかで塗られている。
このグリッドを列または行単位で白黒反転できるとき、矩形範囲全体が黒くできるような矩形範囲の選び方のうち最大面積を答えよ。

解法

公式解説とは異なる方法で解いた。
まず左端Lを順次総当たりしていくことを考える。

左端Lを決めたとき、得られる最大面積を考えよう。
i行目と(i+1)行目を同時に矩形範囲に含めようとした場合、左端Lに対し右端をどこまで右に持って行けるか考えよう。
L列目のi行目と(i+1)行目が等しいなら、以後2つの行が等しい列の右端、i行目と(i+1)行目が異なるなら、以後2つの行が異なる列の右端である。
この処理はO(NM)で前処理をしておくとO(1)で求められる。

あとはヒストグラム中の最大面積の矩形を求める典型問題に落とし込める。

int H,W;
string S[2020];
int len[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	FOR(y,H-1) {
		int same=W,ns=W;
		for(x=W-1;x>=0;x--) {
			if(S[y][x]==S[y+1][x]) {
				len[y][x]=ns-x;
				same=x;
			}
			else {
				len[y][x]=same-x;
				ns=x;
			}
		}
	}
	
	int ma=max(H,W);
	int step=0;
	FOR(i,W) {
		vector<pair<int,int>> V;
		V.push_back({-1,-1});
		for(y=1;y<=H;y++) {
			
			x=len[y-1][i];
			int f=y;
			while(V.back().second>=x) {
				f=V.back().first;
				ma=max(ma,V.back().second*(y-f+1));
				V.pop_back();
			}
			V.push_back({f,x});
		}
	}
	cout<<ma<<endl;
}

まとめ

いや、本番ヒストグラム中の最大面積の矩形を求める典型問題に落とし込むところまでは早々にできたんだけど、バグがとり切れず終了してしまった。