TopCoderOpen 2013 Round2C Medium TheMountain

さてMedium。
本番は余り考えずHardに行ってしまったけど、「四つ角から考えるだけ…」という意見を見かけたので改めてチャレンジ。
http://community.topcoder.com/stat?c=problem_statement&pm=12299

問題

最大200x200の正の整数からなる行列を考える。
このうち、最大50個まで要素が指定される。

ここで、指定されてない要素に正の整数を入れ、行列中のある要素を最大値として、その要素から離れた方向の要素に向かうと数値が真に単調減少になる行列を作る。
そのような行列のうち、値の総和の最小値を答える。

解法

まず、四つ角から値を埋めていった際の最小値を求める。

例えば左上に1を配置し、各要素が上の要素および左の要素より1大きい要素で埋めていく。
ただし、要素が指定されている場合はその値で埋める。
指定要素を埋めると上や左の要素より小さくなる場合、その要素やその右下の要素は左上から単調増加するだけでは辿りつけない。

さらに各要素について、その要素の右上にある数の累積値を計算する。

同様に右上から左下向き、左下から右上向き、右下から左上を処理する。
ここまで行列の幅Nに対してO(N^2)。

次に、行列の各要素が頂点となる場合の累積値を求め、最小値を求めていく。

例えば、今行列中以下のXの要素が頂点となる場合の累積値を求めるとする。

AAAAAIBBBBB
AAAAAIBBBBB
AAAAAIBBBBB
JJJJJXKKKKK
CCCCCLDDDDD
CCCCCLDDDDD
CCCCCLDDDDD

左上に相当するAの領域は、左上から右下方向に数値を増やして埋めたときの値になる。
同様にBは右上、Cは左下、Dは右下から順に埋めた値になる。
これらの領域の累積値は先の事前処理の結果O(1)で求められる。

Iの領域は、左上から値を埋めた場合と右上から値を埋めた場合の最大値を取る。
同様にJ,K,Lの領域は２方向から埋めた値の最大値を取って、その和を取るのでO(N)。
最後のXは、４方向から値を埋めたときの最大値になる。

よって、各要素を頂点とする場合の累積和はO(N)で求められるので、全体でO(N^3)で済む。
(I,J,K,Lの累積和も先に事前処理しておいてもよい)

class TheMountain {
	int mat[202][202];
	int dp[4][202][202];
	int dpt[4][202][202];
	public:
	int minSum(int H, int W, vector <int> rowIndex, vector <int> columnIndex, vector <int> element) {
		int i,x,y,z;
		int N=rowIndex.size();
		
		ZERO(mat);
		ZERO(dp);
		ZERO(dpt);
		FOR(i,N) mat[rowIndex[i]][columnIndex[i]]=element[i];
		
		
		// 右下
		dp[0][0][0]=max(1,mat[0][0]);
		for(i=1;i<=H+W-1;i++) {
			for(y=0,x=i;y<H&&x>=0;y++,x--) {
				if(x>=W) continue;
				z = 1+max((y==0)?0:dp[0][y-1][x], (x==0)?0:dp[0][y][x-1]);
				if(mat[y][x]==0) dp[0][y][x]=z;
				else if(z<=mat[y][x])  dp[0][y][x]=mat[y][x];
				else dp[0][y][x]=3000;
			}
		}
		//右上
		dp[1][H-1][0]=max(1,mat[H-1][0]);
		for(i=1;i<=H+W-1;i++) {
			for(y=H-1,x=i;y>=0&&x>=0;y--,x--) {
				if(x>=W) continue;
				z=1+max((y==H-1)?0:dp[1][y+1][x], (x==0)?0:dp[1][y][x-1]);
				if(mat[y][x]==0) dp[1][y][x]=z;
				else if(z<=mat[y][x])  dp[1][y][x]=mat[y][x];
				else dp[1][y][x]=3000;
			}
		}
		
		//左下
		dp[2][0][W-1]=max(1,mat[0][W-1]);
		for(i=1;i<=H+W-1;i++) {
			for(y=0,x=W-1-i;y<H&&x<W;y++,x++) {
				if(x<0) continue;
				z=1+max((y==0)?0:dp[2][y-1][x], (x==W-1)?0:dp[2][y][x+1]);
				if(mat[y][x]==0) dp[2][y][x]=z;
				else if(z<=mat[y][x])  dp[2][y][x]=mat[y][x];
				else dp[2][y][x]=3000;
			}
		}
		
		//左上
		dp[3][H-1][W-1]=max(1,mat[H-1][W-1]);
		for(i=1;i<=H+W-1;i++) {
			for(y=H-1,x=W-1-i;y>=0&&x<W;y--,x++) {
				if(x<0) continue;
				z=1+max((y==H-1)?0:dp[3][y+1][x], (x==W-1)?0:dp[3][y][x+1]);
				if(mat[y][x]==0) dp[3][y][x]=z;
				else if(z<=mat[y][x])  dp[3][y][x]=mat[y][x];
				else dp[3][y][x]=3000;
			}
		}
		
		FOR(y,H) {
			z=0;
			FOR(x,W) { z+=dp[0][y][x]; dpt[0][y][x]=z+((y==0)?0:dpt[0][y-1][x]);} //右下
			z=0;
			for(x=W-1;x>=0;x--) { z+=dp[2][y][x]; dpt[2][y][x]=z+((y==0)?0:dpt[2][y-1][x]);} //左下
		}
		for(y=H-1;y>=0;y--) {
			z=0;
			FOR(x,W) { z+=dp[1][y][x]; dpt[1][y][x]=z+((y==H-1)?0:dpt[1][y+1][x]);} //右上
			z=0;
			for(x=W-1;x>=0;x--) { z+=dp[3][y][x]; dpt[3][y][x]=z+((y==H-1)?0:dpt[3][y+1][x]);} //左上
		}
		
		int ma=1<<30;
		FOR(y,H) FOR(x,W) {
			if(dp[0][y][x]>=3000 || dp[1][y][x]>=3000 || dp[2][y][x]>=3000 || dp[3][y][x]>=3000) continue;
			int t=max(max(dp[0][y][x],dp[1][y][x]),max(dp[2][y][x],dp[3][y][x]));
			if(y<H-1 && x<W-1) t+=dpt[3][y+1][x+1];
			if(y>0 && x<W-1) t+=dpt[2][y-1][x+1];
			if(y<H-1 && x>0) t+=dpt[1][y+1][x-1];
			if(y>0 && x>0) t+=dpt[0][y-1][x-1];
			for(i=0;i<y;i++) t += max(dp[0][i][x],dp[2][i][x]); //上
			for(i=y+1;i<H;i++) t += max(dp[1][i][x],dp[3][i][x]); //下
			for(i=0;i<x;i++) t += max(dp[0][y][i],dp[1][y][i]); //右
			for(i=x+1;i<W;i++) t += max(dp[2][y][i],dp[3][y][i]); //左
			ma=min(ma,t);
		}
		
		if(ma==1<<30) return -1;
		return ma;
	}
};

まとめ

コード量が多く面倒だが、550にしては簡単。
「Div2 1000ptみたい」という意見も納得。
コピペ無しに綺麗に書きたいもんだ。

kmjp's blog

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

TopCoderOpen 2013 Round2C Medium TheMountain

問題

解法

まとめ