Codeforces #263 Div1 A. Appleman and Toastman

CF263に参加。B,Cで時間的に手こずった挙句CをTLEしてレート減。
http://codeforces.com/contest/461/problem/A

問題

数値の数列の集合に対し、以下の処理を行う。

• 初期状態は、N要素の数列A[i]１つだけの集合である。
• 先手は集合から１つ数列を選び、後手に渡す。その際数列内の全要素の合計分のスコアを追加する。
• 後手は先手から受け取った数列の要素が１つならその数列を破棄する。２つ以上なら、その数列を２つの空でない数列に分け、先手に返す。

先手後手が集合が空になるまで交互に処理を行い、両者が最善手を取った場合、最大スコアはどの位になるか。

解法

先にA[i]を昇順ソートし、後は以下のように繰り返せばよい。

• 先手は数列が１個しかないのでそれを選ぶ。
• 後手はA[0]とそれ以外に分けて先手に返す。
• 先手はA[0]だけの数列を選ぶ。
• 後手は１要素の数列を渡されるのでそれを破棄する。
• 先手はA[1]～からなる数列１個を持っているので先頭に戻る。

上記処理を繰り返すと、A[i]は(i+2)回ずつ、ただしA[N-1]だけはN回スコアにカウントされることがわかる。

int N,A[400000];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	ll ret=0;
	FOR(i,N-1) ret+=A[i]*1LL*(i+2);
	ret+=A[N-1]*1LL*N;
	cout << ret << endl;
}

まとめ

一見ややこしいけど、最終的なコードはシンプル。