Codeforces #242 Div2 D. Biathlon Track

多分想定より緩い解法で通っている。
http://codeforces.com/contest/424/problem/D

問題

２次元グリッドがあり、各セルには高さがある。
隣接セル間を移動する際、同じ高さのセルを移動するコストTp、上る場合のコストTd、下る場合のコストTuが与えられる。

このグリッド上で１辺３マス以上の長方形のフィールドを取ったとき、周辺部を時計回りに回ったときの総コストがTに近くなる長方形を選択せよ。

解法

事前に左右移動および上下移動時のコストの累積和を取っておけば、後は長方形の左上の点と右下の点を総当たりすればよい。
グリッドの１辺をNセルとするとO(N^4)で処理できる。

実際は想定解法はO(N^3*logN)なようで、４辺のうち３辺まで決めたら４辺目はO(logN)で求める必要があるようだ。

int H,W,T;
int P,U,D;
int V[301][301];
int ML[301][301],MR[301][301],MU[301][301],MD[301][301];


void solve() {
	int f,i,j,k,l;
	int x,y,x1,x2,y1,y2;
	int best=1<<30;
	int bx1,bx2,by1,by2;

	
	cin>>H>>W>>T;
	cin>>P>>U>>D;
	FOR(y,H) FOR(x,W) cin>>V[y][x];
	FOR(y,H) {
		for(x=1;x<W;x++) {
			if(V[y][x]< V[y][x-1]) MR[y][x]=MR[y][x-1]+D;
			if(V[y][x]==V[y][x-1]) MR[y][x]=MR[y][x-1]+P;
			if(V[y][x]> V[y][x-1]) MR[y][x]=MR[y][x-1]+U;
		}
		for(x=W-2;x>=0;x--) {
			if(V[y][x]< V[y][x+1]) ML[y][x]=ML[y][x+1]+D;
			if(V[y][x]==V[y][x+1]) ML[y][x]=ML[y][x+1]+P;
			if(V[y][x]> V[y][x+1]) ML[y][x]=ML[y][x+1]+U;
		}
	}
	FOR(x,W) {
		for(y=1;y<H;y++) {
			if(V[y][x]< V[y-1][x]) MD[y][x]=MD[y-1][x]+D;
			if(V[y][x]==V[y-1][x]) MD[y][x]=MD[y-1][x]+P;
			if(V[y][x]> V[y-1][x]) MD[y][x]=MD[y-1][x]+U;
		}
		for(y=H-2;y>=0;y--) {
			if(V[y][x]< V[y+1][x]) MU[y][x]=MU[y+1][x]+D;
			if(V[y][x]==V[y+1][x]) MU[y][x]=MU[y+1][x]+P;
			if(V[y][x]> V[y+1][x]) MU[y][x]=MU[y+1][x]+U;
		}
	}
	
	FOR(y1,H-2) for(y2=y1+2;y2<H;y2++) FOR(x1,W-2) for(x2=x1+2;x2<W;x2++) {
		int sc=(MR[y1][x2]-MR[y1][x1])+(MD[y2][x2]-MD[y1][x2])+(ML[y2][x1]-ML[y2][x2])+(MU[y1][x1]-MU[y2][x1]);
		if(abs(sc-T)<best) best=abs(sc-T), bx1=x1,bx2=x2,by1=y1,by2=y2;
	}
	_P("%d %d %d %d\n",by1+1,bx1+1,by2+1,bx2+1);
}

まとめ

O(N^4)ならBかCで出てくるレベルの問題な気がする。