TopCoder SRM 645 Div2 Medium ConnectingCars

SRM646のDiv1 Easyと似てるなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13602

問題

1本の長い線路の上にN個の車両がある。
各車両は位置P[i]から長さL[i]を占めている。

各車両を線路に沿って移動させ、全体を１つに連結したい。
各車両の移動距離の総和の最小値を答えよ。

解法

まず全体を位置順にソートしておく。
この問題は、N台の車両のうち真ん中の車両に向かって両側から寄せていくだけで良い。

以下のように考えると理解できる。
左にP台が１個に連結した車両群、右にQ台が１個に連結した車両群があって、これらを連結したいとする。
左のP台を1右に動かすと、移動距離の総和はP増え、右のQ台を1左に動かすと、移動距離の総和はQ増える。
そう考えると少ない方の車両群を動かした方が移動距離の総和が短くなる。

以下のコードでは、念のため各車両を固定してそこに他の車両を寄せるパターンを全部試している。

class ConnectingCars {
	public:
	pair<ll,ll> P[101];
	ll dist[101][101];
	int N;
	long long minimizeCost(vector <int> positions, vector <int> lengths) {
		int i,j,x,y;
		N=positions.size();
		FOR(i,N) P[i]=make_pair(positions[i],lengths[i]);
		sort(P,P+N);
		FOR(y,N) FOR(x,y) {
			ll tot=P[y].first-P[x].first;
			for(i=x;i<y;i++) tot-=P[i].second;
			dist[x][y]=dist[y][x]=tot;
		}
		
		ll mi=1LL<<60;
		FOR(i,N) {
			ll tot=0;
			FOR(j,N) tot+=dist[i][j];
			mi=min(mi,tot);
		}
		
		return mi;
		
	}
}

まとめ

Div2 Mediumにしては簡単だけど、Div2 Easyにしては難しいかも。