kmjp's blog

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

Looksery Cup 2015 : D. Haar Features

ちょっと問題設定がわかりにくいな…。
http://codeforces.com/contest/549/problem/D

問題

N*Mのグリッドが与えられる。
各マスは白(W)か黒(B)である。
このグリッドにおいてV=(Wのマス数)-(Bのマス数)を計算したいが、直接この値を計算することはできない。

グリッドに対し、左上がグリッドの左上と一致するa*bの矩形領域を考える。
この時、任意の定数cに対しc*(a*b)をVに加算することができる。

Vの値を求めるのに、矩形領域を用いたVの加算処理を最小何回行う必要があるか。

解法

この問題は以下のように書き換えることができる。
「各セルは初期値0を持つ。1回の処理で左上がグリッドの左上と重なる矩形領域に含まれるセルに対し、同じ値を加算できる。Wのセルが1、Bのセルが-1となるようにするには最小何回の処理が必要か。」

上記処理を逆に回すことを考える。
すなわち、先に各セルの白黒に合わせて1,-1を埋めておき、ここに上記矩形領域への加算処理を行い全セルを0にしよう。

これには、全セルのうち0でない最も右下のセルを探し、そこを矩形領域の右下とし、そこのセルの値が0になるような値を加算するという処理を繰り返せばよい。
計算量はO(N^2*M^2)かかるがなんとか間に合う。

int H,W;
int D[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>s;
		FOR(x,W) D[y][x]=s[x]=='W'?1:-1;
	}
	
	int ret=0;
	while(1) {
		int ty=-1,tx=-1;
		FOR(y,H) FOR(x,W) if(D[y][x]!=0) ty=y,tx=x;
		if(ty==-1) break;
		ret++;
		FOR(y,ty+1) FOR(x,tx+1) D[y][x]-=D[ty][tx];
	}
	
	cout<<ret<<endl;
}

まとめ

若干の考察は必要だけど、実装は簡単。