Google Code Jam 2011 Round 2 : B. Spinning Blade

GCJ2011のRound2は、本番でAl・Bs・Cl・Dsが解けていたがBlは解けなかったので、復習チャレンジ。
http://code.google.com/codejam/contest/1150486/dashboard#s=p1&a=1

解法

最初に、重さDは全くこの問題に影響しないので無視する。
あとは重心が真ん中にくるような正方形を探すのだが、まじめにやると左上の点の取り方がO(N^2)、辺の長さの取り方がO(N)、重心判定が(角を落とした)正方形内の全部の点の重量を足すのでのO(N^2)かかるのでO(N^5)となる。

smallならN=10なのでこれでも通るし、実際本番はこれで通した。
largeだとN=500なので、通らない。

そこで、重心計算を省力化することを考えた。
各行について、２点間の累積の重さを事前に計算し、各列も同様に２点間の重さを事前に計算しておく。

２点間の重さといってもメモリ量はO(N^2)じゃなくO(N)でよい。
行でいえば、左端と各x座標までの累積をとっておけば、差をとって任意のx座標間の累積和をとれる。

重心判定では、正方形内の各行について累積重さにY座標の距離をまとめて掛けることで、X軸方向のfor文を外すことができる。
列についても同様。
これでO(N^4)かな。実際は辺の長さがもっと小さいケースも多いので、O(N^4)より小さい。
実際、Largeでも１ケースだけ19秒かかったがあとは１秒以下。

int R,C,D;
int P[201],V[201];
char field[501][501];
int RW[501][501];
int CW[501][501];
int maxv;

int test(int x,int y,int K){
	int sum[3][3];
	int tx,ty,ix,iy,sx,sy;
	ZERO(sum);
	
	sx=sy=0;
	if(K%2==0) {
		//行の処理
		for(ty=y;ty<y+K;ty++) {
			if(ty==y || ty==y+K-1) sy += (RW[ty][x+K-1]-RW[ty][x+1]) * (ty*2 - (y*2+(K-1)));
			else sy += (RW[ty][x+K]-RW[ty][x]) * (ty*2 - (y*2+(K-1)));
		}
		//列
		for(tx=x;tx<x+K;tx++) {
			if(tx==x || tx==x+K-1) sx += (CW[tx][y+K-1]-CW[tx][y+1]) * (tx*2 - (x*2+(K-1)));
			else sx += (CW[tx][y+K]-CW[tx][y]) * (tx*2 - (x*2+(K-1)));
		}
	}
	else {
		//行の処理
		for(ty=y;ty<y+K;ty++) {
			if(ty==y || ty==y+K-1) sy += (RW[ty][x+K-1]-RW[ty][x+1]) * (ty - (y+K/2));
			else sy += (RW[ty][x+K]-RW[ty][x]) * (ty - (y+K/2));
		}
		//列
		for(tx=x;tx<x+K;tx++) {
			if(tx==x || tx==x+K-1) sx += (CW[tx][y+K-1]-CW[tx][y+1]) * (tx - (x+K/2));
			else sx += (CW[tx][y+K]-CW[tx][y]) * (tx - (x+K/2));
		}
	}
	
	if(sx==0 && sy==0) return 1;
	return 0;
}


int check(int K) {
	int x,y;
	
	//左上のポイントを探す
	for(y=0;y<=R-K;y++) {
		for(x=0;x<=C-K;x++) {
			if(test(x,y,K))
				return 1;
		}
	}
	return 0;
}


void solve(int _loop) {
	int i,j,k,result,res,dir,ok,state,fstate,up,x,y,sp,dist1,dist2;
	double br,tb1,tb2,start,end;
	char list[1000],ts[2],ress[1000];
	int prep,maxv,st,ed,sv;;
	long long s,t,p;
	
	ZERO(field);
	ZERO(V);
	GET3(&R,&C,&D);
	
	FOR(i,R) {
		GETs(field[i]);
		//_P("%s\n",field[i]);
	}
	ZERO(RW);
	ZERO(CW);
	//各行の重さ
	FOR(y,R) {
		RW[y][0]=0;
		FOR(x,C) {
			RW[y][x+1]=RW[y][x]+field[y][x]-'0';
		}
	}
	//各列の重さ
	FOR(x,C) {
		CW[x][0]=0;
		FOR(y,R) {
			CW[x][y+1]=CW[x][y]+field[y][x]-'0';
		}
	}
	
	k=R;
	if(k>C) k=C;
	for(;k>=3;k--) if(check(k)) break;
	}
	
	if(k<3) {
		_PE("Case #%d: IMPOSSIBLE\n",_loop);
	}
	else {
		_PE("Case #%d: %d\n",_loop, k);
	}
}

まとめ

この累積値を事前に計算しておくってのは最近覚えた。
計算量を落とすのによく使えるね。

今回、重さDのパラメータは全く使ってないわけだけど、GCJでこういうの珍しいな。