Codeforces #214 Div2. E. Dima and Magic Guitar

ちょっと迷ったけど、最終的にすんなり解けた問題。
CやDより楽でした。
http://codeforces.com/contest/366/problem/E

問題

N*Mのグリッドが与えられ、それぞれ音に対応する1～9の数字が書かれている。
さらに、1～9の音で構成された曲が与えられる。
曲の難しさは、連続する音が置かれた２つのセルの最大マンハッタン距離で求められる。

グリッドと曲に対する難しさを答えよ。

解法

曲は最大100000音と多いけど、連続する音のパターンは高々9*9の81通りしかない。
面倒なので、81通りすべての最大マンハッタン距離を求めてしまおう。

２つのセルのマンハッタン距離は(x+y)の差と(y-x)の差の大きい方である。
よって、1～9の各数字において、(x+y)と(y-x)の最大値・最小値を求めておく。
そして２つの数字のペアにおいて、(x+y)同士の差を最大化したものと、(y-x)同士の差を最大化したものの大きい方がその２つの音の最大マンハッタン距離とおける。

int N,M,K,S;
int A[2001][2001];
int num2[2][10][2];
int mat[10][10];

void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M>>K>>S;
	FOR(i,10) {
		num2[0][i][0]=4000;
		num2[0][i][1]=0;
		num2[1][i][0]=4000;
		num2[1][i][1]=0;
	}
	FOR(y,N) FOR(x,M) {
		cin>>r;
		num2[0][r][0]=min(num2[0][r][0],x+y);
		num2[0][r][1]=max(num2[0][r][1],x+y);
		num2[1][r][0]=min(num2[1][r][0],y-x+2000);
		num2[1][r][1]=max(num2[1][r][1],y-x+2000);
	}
	FOR(i,S) {
		cin>>x;
		if(i>0) mat[x][y]++,mat[y][x]++;
		y=x;
	}
	
	r=0;
	FOR(y,10) FOR(x,10) if(mat[x][y]) {
		r = max(r, abs(num2[0][x][0]-num2[0][y][0]));
		r = max(r, abs(num2[0][x][1]-num2[0][y][0]));
		r = max(r, abs(num2[0][x][0]-num2[0][y][1]));
		r = max(r, abs(num2[0][x][1]-num2[0][y][1]));
		r = max(r, abs(num2[1][x][0]-num2[1][y][0]));
		r = max(r, abs(num2[1][x][1]-num2[1][y][0]));
		r = max(r, abs(num2[1][x][0]-num2[1][y][1]));
		r = max(r, abs(num2[1][x][1]-num2[1][y][1]));
	}
	_P("%d\n",r);
	
}

まとめ

マンハッタン距離が出たら(x+y)と(y-x)で置き換えるの、以前SRMでもあったな。
最初は頭の中で「斜めの走査線をずらしていけばいいんじゃね？」と思い浮かんだけど、式にしてみたら結局既知のテクニックだった。