kmjp's blog

競技プログラミング参加記です

Codeforces #248 Div1 B. Nanami's Digital Board

Codeforces

また面倒な問題。
http://codeforces.com/contest/434/problem/B

問題

NxMの２次元グリッドがあり、各セルは0または1の値を持つ。
ここで以下２種類のクエリ計Q個に答えよ。

  1. セル(i,j)の値を01反転する。
  2. セル(i,j)について、1だけで構成された長方形のうち、セル(i,j)が外周に来る最大面積のものを答えよ。

解法

各セルについて、その上下左右それぞれ1が連続する数を求めておく。
1番目のクエリに対しては、DPでこの値はO(N+M)で更新できる。

2番目のクエリについては、そのセルが長方形の上辺・下辺・右辺・左辺に来る場合それぞれで、そのセルを含む最大長方形を求めればよい。
例えば、そのセル(#)を下辺とする最大長方形(*)のイメージは下記のとおりである。

   1                1
 1 1 11  1        1 1 11  1
 1111111 1        ******* 1  
 111111111  →    ******* 1 
11111#11111      1****#**111


この最大長方形の求め方は、「ヒストグラム 最大長方形」などで検索するとスタックを用いた方法が見つかる。
事前に各セルの上に連続する1の数は計算済みなので、この処理はO(N)で処理できる。

上辺・下辺・右辺・左辺について同様に処理を行うと、全部でQ個のクエリをO((N+M)*Q)で処理出来る。

int N,M,Q;
int A[1001][1001];
int B[4][1024][1024];

void solve() {
	int f,i,j,k,l,x,y,ty,tx;
	cin>>N>>M>>Q;
	
	FOR(y,N) FOR(x,M) cin>>A[y][x];
	FOR(y,N) FOR(x,M) B[0][y][x]=(A[y][x])?(1+((x>0)?B[0][y][x-1]:0)):0;
	FOR(y,N) for(x=M-1;x>=0;x--) B[1][y][x]=(A[y][x])?(1+(B[1][y][x+1])):0;
	FOR(y,N) FOR(x,M) B[2][y][x]=(A[y][x])?(1+((y>0)?B[2][y-1][x]:0)):0;
	for(y=N-1;y>=0;y--) FOR(x,M) B[3][y][x]=(A[y][x])?(1+(B[3][y+1][x])):0;
	
	while(Q--) {
		cin>>i>>ty>>tx;
		tx--,ty--;
		if(i==1) {
			A[ty][tx]^=1;
			FOR(x,M) B[0][ty][x]=(A[ty][x])?(1+((x>0)?B[0][ty][x-1]:0)):0;
			for(x=M-1;x>=0;x--) B[1][ty][x]=(A[ty][x])?(1+(B[1][ty][x+1])):0;
			FOR(y,N) B[2][y][tx]=(A[y][tx])?(1+((y>0)?B[2][y-1][tx]:0)):0;
			for(y=N-1;y>=0;y--) B[3][y][tx]=(A[y][tx])?(1+(B[3][y+1][tx])):0;
			
		}
		else if(A[ty][tx]==0) cout << 0 << endl;
		else {
			ll ret=1;
			FOR(i,4) {
				vector<pair<int,int> > V;
				V.push_back(make_pair(0,-1));
				if(i<2) {
					j=B[i][ty][tx];
					for(y=ty-(B[2][ty][tx]-1);y<=ty;y++) {
						k=min(j,B[i][y][tx]);
						while(V.size()>1 && V[V.size()-2].first>=k) V.pop_back();
						if(V.back().first>=k) V.back().first=k;
						else V.push_back(make_pair(k,y));
					}
					for(y=ty;y<ty+B[3][ty][tx];y++) {
						j=min(j,B[i][y][tx]);
						while(V.size()>1 && V[V.size()-2].first>=j) {
							ret=max(ret,V.back().first*(ll)(y-V.back().second));
							V.pop_back();
						}
						ret=max(ret,V.back().first*(ll)(y-V.back().second));
						V.back().first=min(V.back().first,j);
					}
					ITR(it,V) ret=max(ret,min(j,it->first)*(ll)(ty+B[3][ty][tx]-it->second));
				}
				else {
					j=B[i][ty][tx];
					for(x=tx-(B[0][ty][tx]-1);x<=tx;x++) {
						k=min(j,B[i][ty][x]);
						while(V.size()>1 && V[V.size()-2].first>=k) V.pop_back();
						if(V.back().first>=k) V.back().first=k;
						else V.push_back(make_pair(k,x));
					}
					for(x=tx;x<tx+B[1][ty][tx];x++) {
						j=min(j,B[i][ty][x]);
						while(V.size()>1 && V[V.size()-2].first>=j) {
							ret=max(ret,V.back().first*(ll)(x-V.back().second));
							V.pop_back();
						}
						ret=max(ret,V.back().first*(ll)(x-V.back().second));
						V.back().first=min(V.back().first,j);
					}
					ITR(it,V) ret=max(ret,min(j,it->first)*(ll)(tx+B[1][ty][tx]-it->second));
				}
			}
			cout << ret << endl;
		}
	}
	
}

まとめ

ヒストグラムの解法を知っていたので、アプローチはすんなり思い浮かんだが正解するまでだいぶバグを作りこんで手間取った。