TopCoder SRM 669 Div2 Medium CombiningSlimes

SRM669に参加。Easyで(終わってみると不要だった)ResubmitするわMedium解けないわグダグダだったが、7Challenge決めて赤復帰。
http://community.topcoder.com/stat?c=problem_statement&pm=13947

問題

N個に分裂したスライムがおり、各サイズはA[i]である。
サイズがxとyの２つのスライムを合体させると、そのサイズx+yの１個のスライムになる。
その際、x*yのポイントが得られる。

N個のスライムを最適な順で合体させて１個にした場合、ポイントの最大値はいくつになるか。

解法

試してみると、合体順は関係ないことがわかる。
例えばA={a, b, c}で適当に連結させると、ab+bc+ca = (a(b+c) + b(c+a) + c(a+b))/2である。
もっと一般的に書くと、である。

良く考えてみると、スライムを連結させる過程で元i番のスライムとj番のスライムは１回だけ合体するのでA[i]*A[j]が１回だけ最終ポイントに寄与することがわかる。
あとは上記式を求めるだけ。

class CombiningSlimes {
	public:
	int maxMascots(vector <int> a) {
		int tot=0;
		int sum=0;
		FORR(r,a) tot+=r;
		FORR(r,a) sum+=r*(tot-r);
		return sum/2;
	}
}

まとめ

これがわかっているとDiv1 Easyがむちゃくちゃ簡単。