TopCoder SRM 577 Div1 Medium EllysChessboard

ちょっと古いけど解けてない問題だったので。
http://community.topcoder.com/stat?c=problem_statement&pm=12527

問題

8x8のチェス盤のいくつかに駒が置かれた状態が与えられ、それを再現したい。
最初空の状態のチェス盤に駒を追加していくが、2個目以降の駒を置く際、すでに置いてある駒のうちもっともマンハッタン距離が遠い駒までの距離の分コストがかかる。
再現にかかる総コストを最小化し、その値を答えよ。

解法

Editorialが非常にわかりやすい。

元の座標を(x,y)→(x+y,x-y)で45度変換すると、2点間(p1,q1)-(p2,q2)のマンハッタン距離はmin(|p1-p2|,|q1-q2|)と簡単に記載できる。
(Editorialでは数式で書いているけど、元の座標で1マス移動することが、変換後の座標で斜め移動することに相当することを考えると幾何的にわかりやすい)

変換後の座標において、すでに駒を置いてある範囲を矩形で表現する。
この矩形内の駒が設置済みの場合、駒を全部置くまでの最小コストをメモ化再帰で求めていく。

この矩形の左端・右端・上端・下端を1マスずつ拡張していくことを考える。
拡張したことで新たに矩形に入る駒があった場合、そのコストは元の矩形の左端・右端・上端・下端と新規駒のマスを比較することで計算でき、矩形内のコマを1つ1つ比較しなくてもよい。
上記処理を繰り返して処理できる。

矩形の形状は左端・右端・上端・下端でO(N^4)の状態を持つ。
また、各々で最大(N^2)個の駒の内外判定およびコスト判定をするので、O(N^6)程度の時間で解ける。

class EllysChessboard {
	public:
	int B[20][20];
	int memo[20][20][20][20];
	vector<int> X,Y;
	
	int dp(int l,int t,int r,int b) {
		if(memo[l][t][r][b]==-1) {
			ll mask=0;
			int i,j;
			FOR(i,X.size()) if(X[i]<l || X[i]>r || Y[i]<t || Y[i]>b) mask |= 1LL<<i;
			if(mask==0) return memo[l][t][r][b]=0;
			
			memo[l][t][r][b] = 1<<30;
			FOR(i,4) {
				int nl=l-(i==0);
				int nr=r+(i==1);
				int nt=t-(i==2);
				int nb=b+(i==3);
				int mc=0;
				if(nl<0 || nr>=16 || nt<0 || nb>=16) continue;
				
				FOR(j,X.size()) if((mask & (1LL<<j)) && X[j]>=nl && X[j]<=nr && Y[j]>=nt && Y[j]<=nb) {
					mc += max(max(X[j]-nl,nr-X[j]),max(Y[j]-nt,nb-Y[j]));
				}
				memo[l][t][r][b] = min(memo[l][t][r][b], mc + dp(nl,nt,nr,nb));
			}
		}
		return memo[l][t][r][b];
	}
	
	int minCost(vector <string> board) {
		int i,j,x,y;
		ZERO(B);
		MINUS(memo);
		
		X.clear();
		Y.clear();
		FOR(y,8) FOR(x,8) if(board[y][x]=='#') {
			B[x+y+1][x-y+8]=1;
			X.push_back(x-y+8);
			Y.push_back(x+y+1);
		}
		
		if(X.size()<=1) return 0;
		
		int mc=1<<30;
		FOR(i,X.size()) mc=min(mc,dp(X[i],Y[i],X[i],Y[i]));
		return mc;
	}
};

まとめ

マンハッタン距離の問題では、45度回転をするのは定石のようだ。
これは覚えておかなくては。