TopCoder SRM 659 Div2 Medium PublicTransit

SRM659は不参加。
Div1 Mediumは自力で正答したけど、時間がかかりすぎて本番だと間に合わなかったかも。
http://community.topcoder.com/stat?c=problem_statement&pm=13793

問題

R*Cのグリッドがあるとする。

このグリッド上で2か所のセルにワープホールを置くことができる。
ワープホールのあるセルに到達すると、瞬時にもう一つのワープホールのあるセルに移動できる。
(ワープホールのあるセルに到達しても必ずしも使わなくてもよい)

隣接セルに移動するのにかかる時間を1とする。
適切なワープホールの位置を選択し、全2セル対間の移動時間の最大値を最小化せよ。

解法

ワープホールのセルをP,Qとする。
2点(S,T)間の最短移動時間は以下の最小値に一致する。
それぞれ定数時間で計算できる。

• S→Tのマンハッタン距離
• S→Pのマンハッタン距離 + Q→Tのマンハッタン距離
• S→Qのマンハッタン距離 + P→Tのマンハッタン距離

あとはワープホールの2セルP,Qを総当たりし、頂点対S,Tを総当たりすればO((RC)^4)で処理できる。
移動時間の計算に、最短経路だからとダイクストラなどより計算コストの高い手法を使わないようにしよう。

class PublicTransit {
	public:
	int minimumLongestDistance(int R, int C) {
		int mi=100;
		int x1,y1,x2,y2;
		int x3,y3,x4,y4;
		FOR(x1,R) FOR(y1,C) {
			FOR(x2,R) FOR(y2,C) {
				int ma=0;
				FOR(x3,R) FOR(y3,C) {
					FOR(x4,R) FOR(y4,C) {
						int d=abs(x3-x4)+abs(y3-y4);
						int d1=abs(x3-x1)+abs(y3-y1) + abs(x4-x2)+abs(y4-y2);
						int d2=abs(x3-x2)+abs(y3-y2) + abs(x4-x1)+abs(y4-y1);
						ma=max(ma,min(d,min(d1,d2)));
					}
					if(ma>=mi) break;
				}
				mi=min(mi,ma);
			}
		}
		return mi;
	}
}

まとめ

Div2 Mediumにしても愚直すぎる気がするけど、なんでこれを選んだのだろう。
移動の最短時間をO(1)で求められるか気づくかが焦点？