Codeforces #198 Div1. A. Tourist Problem

CF#198は参加したけど、pretest突破にだいぶ手こずったうえ、Cが普段に比べ妙に簡単だったようでせっかく３問解いたのに微妙な順位に終わった。
http://codeforces.com/contest/341/problem/A

問題

１直線上にN個の町があり、それぞれ初期位置から距離A[i]の場所に配置されている。
ここで、初期位置から全部の町を順にまわり、最後の町に到着したら終了する。

任意の順で町を回る場合、移動距離の平均値を答えよ。

解法

移動順はN!通りあるが、そのうちi番目の町の次にj番目の町に行くのは、i番を最後以外に回る(N-1)通りに配置し、iとj以外の(N-2)要素を任意の順で配置するの組み合わせ(N-2)!とかけると結局(N-1)!通りである。
よって平均値には|A[i]-A[j]|*(N-1)!/N! = |A[i]-A[j]|/Nだけ寄与する。

よって、最初の１手は初期位置から移動することを考えると求める値は以下の通り。

後者はi,jで２重ループを行うとTLEするので、先にAをソートして部分和を計算して置くと、A[i]に対しA[0]～A[i-1]はA[i]未満であり、A[i+1]～A[N-1]がA[i]より大きいことを利用して１重ループで計算できる。

ll N;
vector<ll> A,T;
ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}

void solve() {
	int f,r,i,j,k,l, x,y;
	ll tot=0,Q;
	
	cin>>N;
	FOR(i,N) A.push_back(GETi());
	sort(A.begin(),A.end());
	FOR(i,N) {
		tot+=A[i];
		T.push_back(tot);
	}
	
	Q=N;
	FOR(i,N) {
		tot += ((T[N-1]-T[i])-A[i]*(N-(i+1)));
		if(i>0) tot +=  (i*A[i] - T[i-1]);
	}
	
	ll G=gcd(tot,Q);
	tot/=G;
	Q/=G;
	_P("%lld %lld\n",tot,Q);
}

まとめ

本番４回もpretestミスしたのが痛い。