Codeforces #186 Div2. C. Ilya and Matrix

CF186はDiv2なので不参加。
http://codeforces.com/contest/313/problem/C

問題

2^N×2^Nの整数要素からなる正方行列を考える。
ここで、以下のアルゴリズムで行列の美しさを求める。

• 行列の最大要素の値をmとする。
• N=0ならmが美しさである。N>0なら、2^N×2^Nの行列を4つの2^(N-1)×2^(N-1)の行列に分け、mに4つの行列の美しさを足したものが全体の美しさになる。

4^N個の数字が与えられたとき、その値を2^N×2^Nの行列に配置した際、得られる美しさを最大化せよ。

解法

2^N×2^N行列から2^(N-1)×2^(N-1)行列を4つ作るとき、それぞれの美しさの和を最大化するのは、元の行列の上位4つがそれぞれの4つの行列に配置すればよい。
上記処理を同様に考えていくと、1番大きい要素はN回、4番目までに大きい要素は(N-1)回、・・・・4^i番目までに大きい要素は(N-i)回美しさに寄与する。

よって、各要素を大きい順にソートし、要素数を1/4しながら数列の和を加算していけばよい。

int N;
int A[2000002];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>x;
	FOR(i,x) A[i]=GETi();
	sort(A,A+x);
	reverse(A,A+x);
	
	ll tot=0;
	while(x) {
		FOR(i,x) tot+=A[i];
		x>>=2;
	}
	cout << tot << endl;
	return;
}

まとめ

Div2とはいえCの割に簡単。Div1 A相当ってことだしね。