読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #242 Div2 D. Biathlon Track

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

問題

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

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

解法

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

実際は想定解法はO(N^3*logN)なようで、4辺のうち3辺まで決めたら4辺目は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で出てくるレベルの問題な気がする。

広告を非表示にする