SRM diary(Sigmar)

Google Code Jam 2011 Round 2 B Spinning Blade

Google Code Jam | 21:25 |

Problem Statement

解答方針

よくある普通のDPに見えるのだが何かうまく計算できなくてとりあえずsmallを全探索しようとし始める

サンプル合ったのでsmall提出。WA。おいおい・・・

（Kが偶数のときと奇数のときで重心位置が0.5刻みになるのに1刻みみたいに書いていたのが原因）

・・・

・・・

（すでにコンテスト開始から1時間経過）

よくわからないので再度Largeを真面目に考え始める

やはりDPだ

モーメントの計算方法Σ(p-c)*mass(p)を変形すると、Σp*mass(p)-c*Σmass(p)

従ってある正方形のp*mass(p)とmass(p)の和を記憶しておけば定数時間でモーメントを計算できる（⇔重心が中心にあるか判定できる）

ある長方形のΣmass(p)を求めるDPは、左上隅(0,0)～右下隅(r-1,c-1)までの長方形の重さをsum[r][c]、位置(r,c)の重さをmass[r][c]とすると、sum[r][c]=sum[r-1][c]+sum[r][c-1]-sum[r-1][c-1]+mass[r-1][c-1]で計算できる

このDPを使って、左上隅(r,c)～右下隅(r+k-1,c+k-1)の正方形の重さを求めるには、sum[r+k][c+k]-sum[r][c+k]-sum[r+k][c]+sum[r][c]を求めれば良い

あとは4隅の重さを引けば求めたいものが求められる

Σp*mass(p)はr成分とc成分に分けるとやはり同様に計算できる

DP部分の計算はO(R*C)

あとは正方形の位置と大きさを定めれば定数時間でモーメントが計算できるので、計算量はO(R*C*min(R,C))≒500^3程度

というDPを書くのにバグりまくってとんでもないことになった

mass[r][c]を事前計算せず混乱してしまったのが大きな過ちだった

提出時間：Large 1h44m41s

ソースコード

変数対応表

Σp*mass(p)→(msumr, msumc)

p*mass(p)→(mwr, mwc)

Σmass(p)→sum

入出力は省略。IMPOSSIBLEのときは-1を返す。

int solve(int R, int C, int D, vector <string> bl) {
	int res=-1;

	ll msumr[510][510];
	ll msumc[510][510];
	ll sum[510][510];
	ll mwr[510][510];
	ll mwc[510][510];
	memset(msumr, 0, sizeof(msumr));
	memset(msumc, 0, sizeof(msumc));
	memset(sum, 0, sizeof(sum));
	memset(mwr, 0, sizeof(mwr));
	memset(mwc, 0, sizeof(mwc));

	for(int r=0; r<R; r++) {
		for(int c=0; c<C; c++) {
			mwr[r][c]=r*(D+bl[r][c]-'0');
			mwc[r][c]=c*(D+bl[r][c]-'0');
		}
	}

	for(int r=1; r<=R; r++) {
		for(int c=1; c<=C; c++) {
			sum[r][c]=sum[r][c-1]+sum[r-1][c]-sum[r-1][c-1]+D+bl[r-1][c-1]-'0';
			msumr[r][c]=msumr[r][c-1]+msumr[r-1][c]-msumr[r-1][c-1]+mwr[r-1][c-1];
			msumc[r][c]=msumc[r][c-1]+msumc[r-1][c]-msumc[r-1][c-1]+mwc[r-1][c-1];
		}
	}

	for(int r=0; r<R; r++) {
		for(int c=0; c<C; c++) {
			for(int k=3; k<=min(R, C); k++) {
				if(r+k>R || c+k>C) break;
				ll sumr=0, sumc=0;
				sumr=msumr[r+k][c+k]-msumr[r+k][c]-msumr[r][c+k]+msumr[r][c]-mwr[r][c]-mwr[r+k-1][c]-mwr[r][c+k-1]-mwr[r+k-1][c+k-1];
				sumr*=2;
				sumr-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(r*2+k-1);
				sumc=msumc[r+k][c+k]-msumc[r+k][c]-msumc[r][c+k]+msumc[r][c]-mwc[r][c]-mwc[r+k-1][c]-mwc[r][c+k-1]-mwc[r+k-1][c+k-1];
				sumc*=2;
				sumc-=(sum[r+k][c+k]-sum[r+k][c]-sum[r][c+k]+sum[r][c]-(D+bl[r][c]-'0')-(D+bl[r+k-1][c]-'0')-(D+bl[r][c+k-1]-'0')-(D+bl[r+k-1][c+k-1]-'0'))*(c*2+k-1);
				if(sumr==0 && sumc==0) res=max(res, k);
			}
		}
	}

	return res;
}