東京工業大学プログラミングコンテスト2015 : E - マス目色ぬり

ここから100pt問題。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_e

問題

N*Nの白黒市松模様状に塗られたグリッドがある。
このうちK箇所のマスの位置が指定されるので、それらのマスは白黒反転した。

このグリッドの長方形の部分を選択したとき、白マスと黒マスの差は最大どれだけ開くか。

解法

白黒反転を行わない場合、奇数マス分の長方形を選んだ時白黒マスの差は1開く。
これ以上差を開かせるには、反転したマスを含んでいくしかない。

そこで、Kマス分の白黒反転後に累積和を取り、長方形内の白黒マスの差をO(1)で求められるようにしておく。
次に各反転マスを含むか含まないか2^K通り総当たりする。
各ループでは、含むことにした反転セルをすべて囲う最小の長方形を求め、白黒差を求める。
また、その際左右上下を１マスだけ拡大したものも同時に調べておくとよい。

int N,K;
int X[20],Y[20];
int tot[2020][2020];
int sum[2020][2020];

int range(int L,int T,int R,int B) {
	if(L>R || T>B) return 0;
	if(L<0 || R>=N || T<0 || B>=N) return 0;
	return abs(sum[B+1][R+1] -sum[B+1][L]-sum[T][R+1]+sum[T][L]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) tot[y][x]=((y+x)%2)?1:-1;
	FOR(i,K) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		tot[Y[i]][X[i]]*=-1;
	}
	FOR(y,N) FOR(x,N) sum[y+1][x+1]= sum[y][x+1] + sum[y+1][x] -sum[y][x] +tot[y][x];
	int ma=1;
	for(int mask=1;mask<1<<K;mask++) {
		int L=N-1,R=0,T=N-1,B=0;
		FOR(i,K) if(mask&(1<<i)) L=min(L,X[i]),R=max(R,X[i]),T=min(T,Y[i]),B=max(B,Y[i]);
		
		for(int x1=L-1;x1<=L;x1++) for(int x2=R;x2<=R+1;x2++)
		for(int y1=T-1;y1<=T;y1++) for(int y2=B;y2<=B+1;y2++) ma=max(ma,range(x1,y1,x2,y2));
	}
	
	
	
	cout<<ma<<endl;
}

まとめ

Kが小さいのがミソ。