TopCoderOpen 2014 Round2A Medium NarrowPassage

本番にすべてのケースを考えきれなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=13184

問題

左右の座標0～Lからなる長さLの細い道路上にN匹の狼がおり、それぞれの初期位置とゴール位置が与えられる。
各狼をゴール位置に移動させたいが、細い道路上では他の狼とすれ違うことができない。
ただし、位置0及びLには広い空間があり、ここではすれ違いが可能である。

各狼をゴールに移動させる総移動距離を最小化せよ。

解法

あり得るケースは以下の２つである。

• 元々左側にいる狼x匹が位置0に移動してすれ違った後ゴールに移動し、右側にいるy匹が位置Lに移動してゴールに移動し、残りの真ん中の(N-x-y)匹は両端でのすれ違いを利用せずゴールに直行する。
  • これが有効なのは、左x匹のゴール位置がそれぞれ左x番目までであり、右y匹のゴール位置が右y番目までであり、真ん中の(N-x-y)匹は開始位置とゴール位置における相対位置が維持できる場合である。
  • xとyの取り方がO(N^2)で、後は移動距離の計算にO(N)なのでO(N^3)で計算できる。
• 一旦全員が位置0またはLに退避し、１体ずつ左右で移動してそれ以上すれ違う必要がなくなってから、それぞれゴール位置に移動する。
  • 最初左側何匹が位置0に行くかをO(N)通り取れる。その後１体ずつの移動においてゴール位置が左側何匹目までは左に集まるかが同様にO(N)通り、移動距離の計算も合わせてO(N^3)で計算できる。

class NarrowPassage {
	public:
	
	int minDist(int L, vector <int> a, vector <int> b) {
		int i,x,y,j;
		int N=a.size();
		
		pair<int,int> P[51];
		int tar[51];
		FOR(i,N) P[i]=make_pair(a[i],b[i]);
		
		sort(P,P+N);
		sort(b.begin(),b.end());
		FOR(i,N) FOR(x,N) if(P[i].second==b[x]) tar[i]=x;
		
		int mi=1<<30,tot,ok;
		FOR(x,N+1) FOR(y,N+1) {
			if(x+y>N) continue;
			
			tot=0,ok=1;
			FOR(i,N) {
				if(i<x) tot+=P[i].first+P[i].second, ok &= tar[i]<x;
				else if(i>=x && i<N-y) tot+=abs(P[i].first-P[i].second) , ok &= tar[i]==i;
				else tot+=2*L-P[i].first-P[i].second , ok &= tar[i]>=N-y;
			}
			if(ok) mi=min(mi,tot);
		}
		
		FOR(x,N+1) FOR(y,N+1) {
			tot=0;
			FOR(i,N) {
				if(i<x) {
					if(tar[i]<y) tot+=P[i].first+P[i].second;
					else tot+=P[i].first+L+L-P[i].second;
				}
				else {
					if(tar[i]<y) tot+=L-P[i].first+L+P[i].second;
					else tot+=2*L-P[i].first-P[i].second;
				}
			}
			
			mi=min(mi,tot);
		}
		return mi;
	}
}

まとめ

本番に移動経路を列挙できなかった…。
左端→右端に移動する狼と、右端→左端に移動する狼が同時に存在するケースが思い浮かばず。