C：Tourist Problem
この問題は、スタート地点からの距離がn個与えられ、そのn箇所を全て回る経路の長さの平均を求めるものである。
言い換えれば、与えられた数列Aの任意の並べ替えPについてP1 + |P2 - P1| +…+ |Pn - Pn-1|を計算し、それをn!で割ってやれば良いのである。
・P1部分
P1の部分にA1を固定した時、A2~Anの並べ方（つまりは、P1 = A1であるような経路）は (n-1)!通りであるから、総経路長にA1*(n-1)!を加える。（A2以降も同様）
つまり、P1部分の総和は(A1 + A2 +…+ An) * (n-1)! = S1*(n-1)!となる。
・残りの部分
あるi, jを固定すると、|Aj - Ai|が含まれる経路は、他の項の並べ方の(n-2)!通りと、|Aj - Ai|の位置の(n-1)をかけてやれば良いので、総経路長に|Aj - Ai|*(n-1)!を加える。
つまり、残りの部分の総和は(|Aj - Ai|[任意のi != j])*(n-1)! = S2 * (n-1)!となる。
・S2の部分
そのまま計算するとO(N ^2)でTLEを喰らうことになるので工夫しなければいけない。
そこで、Aを昇順にソートしたものを考える。
Aiについて考えると、A1~Ai-1 < Aiであるから、AiのA1~Ai-1それぞれとの差は(Ai - Ai-1) + (Ai - Ai-2) +…+(Ai - A1) = Ai * (i - 1) - (Ai-1 +…+A1) = Ai * (i - 1) - before_sumとまとめることができる。得られた和をSleftとすると、|Aj - Ai| = |Ai - Aj|よりS2 = 2*Sleftとなる。
最終的な答えは (S1 + 2 * Sleft) / N と表される。
int main(){
LL sum1 = 0, sum2 = 0, bef_sum = 0;
LL n; cin >> n;
LL x[n+1];
rep(i, 1, n+1){
cin >> x[i];
sum1 += x[i];
}
sort(x+1, x+n+1);
rep(i, 1, n+1){
sum2 += x[i] * (i - 1) - bef_sum;
bef_sum += x[i];
}
LL sum = sum1 + 2*sum2;
LL g = gcd(sum, n);
cout << sum/g << " " << n/g << endl;
return 0;
}
D : Bubble Sort Graph
この問題は、与えられた数列に対しバブルソートを行い、スワップが起こった時にその二つを辺で結ぶという操作でグラフを構築し、できたグラフの隣接しない点の個数の最大を求めるものである。n <= 10^5より、グラフでは解けないので注意が必要である。
グラフ上で隣接しない＝間を結ぶ辺がない＝スワップが起こらない
以上のように言い換えることができれば、これが最長部分列問題であることがわかるだろう。
蟻本65ページに最長部分列問題をO(n log n)で解く方法が載っているので参考にして欲しい。