Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-06-05Google Code Jam 2011 Round 2

Google Code Jam 2011 Round 2 B Spinning Blade

| 21:25 | Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) のブックマークコメント

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;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110605