Codeforces #161 Div2. E. Rhombus

さて最後の問題。
http://codeforces.com/contest/263/problem/E

各点の周囲をピラミッド状にスコアをカウントしたときの最大値を答える問題。
数式を見てぱっと思いついたのがAutumnFestのPyramidだった。

ということで今回もimos法でチャレンジ。
imos方で各点に対し、各点の上方向45度までの範囲内の数値の累積値をとっておく。
この累積値を使うと、ある点を中心とした斜め45度の正方形の範囲の累積値がO(1)で計算できる。
よって、この問題では各点を中心に半径1～Kまでの正方形の累積値を合計するのがO(K)。
計算対象の座標は(N-K)(M-K)なので全体はO( (N-K)(M-K)K )。

N<=1000、M<=1000なので、K=666当たりで計算量が最大だけど、それでも約2秒。
タイムリミットは３秒なので何とかクリア。
これでTLEするなら、正方形の累積値を以前の計算値の差分とか使って計算するとこだったが、力技でなんとかなってよかった。

int H,W,K;
ll val[1001][1001];
ll le[1001][1001];
ll ri[1001][1001];
ll up[1001][1001];
ll sc[1001][1001];

void solve() {
	int f,r,i,j,k,l,cur,tar,ret,loop;
	int x,y,mx,my;
	
	GET3(&H,&W,&K);
	FOR(y,H) FOR(x,W) val[x][y]=GETi();
	FOR(y,H) FOR(x,W) {
		le[x][y]=ri[x][y]=up[x][y]=val[x][y];
		if(y>=1) {
			if(x>=1){
				le[x][y]+=le[x-1][y-1];
				up[x][y]+=le[x-1][y-1];
			}
			if(x<W-1){
				ri[x][y]+=ri[x+1][y-1];
				up[x][y]+=ri[x+1][y-1];
			}
			up[x][y]+=up[x][y-1];
		}
	}
	K--;
	ll ma=-1;
	
	for(y=K;y<H-K;y++) for(x=K;x<W-K;x++) {
		for(i=0;i<=K;i++) {
			ll tsc=up[x][y+i];
			if(y>0) {
				tsc-=up[x+i][y-1]+up[x-i][y-1];
				if(x-i-1>=0) tsc-=le[x-i-1][y-1];
				if(x+i+1<W) tsc-=ri[x+i+1][y-1];
			}
			if(y>i) tsc+=up[x][y-i-1];
			
			sc[x][y]+=tsc;
		}
		if(sc[x][y]>ma) {
			ma=sc[x][y];
			mx=x;my=y;
		}
	}
	
	_P("%d %d\n",my+1,mx+1);
	
	return;
}

まとめ

そこまで複雑ではないimos法の問題だった。
いい練習になったね。