torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 669, Division 2, Level 2 : CombiningSlimes

問題概要

 初めに正整数の多重集合 $a$ がある.$|a| > 1$ である間,以下の操作をする.

  1. $a$ から要素を 2 つ取り除き,それらを $x, y$ とする.
  2. $a$ に $x + y$ を加える
  3. $xy$ のスコアを得る

 得られる累計スコアの最大値を求めよ.
 $2 \leq |a| \leq 100$

解法

 $|a| = N$ とします.
 Division 1, Level 1 の類題です.マージの手順も Div1 Edition での分割と同様に二分木で表すことができます.また,最終的なスコアは初期状態のみに依存して,マージの手順には依存しないことも分かります.$a$ による最終スコアは $\sum_{ i = 0 }^{ N - 1 } a_i = s$ として,$$\frac{ \sum_{ i = 0 }^{ N - 1 }a_i( s - a_i ) }{ 2 }$$ となります.
 $a$ の総和を求めるのに $O( N )$ 時間,スコアの計算にも $O( N )$ 時間かかるので,全体でも $O( N )$ 時間です.

コード

#define ALL( c ) begin( c ), end( c )

class CombiningSlimes
{
public:
	int maxMascots( vector <int> a )
	{
		const int sum = accumulate( ALL( a ), 0 );
		transform( ALL( a ), begin( a ), [=]( const int s ){ return s * ( sum - s ); } );
		return accumulate( ALL( a ), 0 ) / 2;
	}
};