Codeforces #186 Div2 C "Ilya and Matrix"
問題
http://codeforces.com/contest/313/problem/C
訳
イリヤはとても気立てのよいライオンだ。彼は数学が好きである。数学のオブジェクトの中で、彼がすきなのは行列である。今、彼は複雑な行列の問題を解かなければならない。
2^n * 2^nサイズの正方形の行列と4^nの整数がある。これらの数を行列に(1つのセルに1つの数を)配置し、そして結果としてできた行列の美しさを最大化する必要がある。
2^n * 2^nサイズの行列の美しさは、下記のアルゴリズムから得られる整数である。
1. 行列の要素から最大の数を見つける。それをmとしよう。 2. もしn = 0であれば、行列の美しさはmと等しい。 そうでなければ、行列は4つの2^(n-1) * 2^(n-1)サイズの サブ行列にわけることができる。 そして、行列の美しさはmと4つのサブ行列の美しさの総和と等しい
このアルゴリズムは再帰的に適用される。
イリヤを助けるため、課題を解決し、行列の美しさ最大値を出力せよ。
制約
1 <= 4^n <= 2 * 10^6
1 <= 配置する数の値 <= 10^9
考えた事
つまりだ、足せる数が4分の1ずつ減ってくってことだ。
ソートして、合計値出して、インデックスを4分の1に減らしてって総和をだせばよい。
ソースコード
typedef long long I64; I64 a[2000050]; int main() { int n; cin >> n; for( int i = 0; i < n; i++ ){ cin >> a[i+1]; } // 降順にソート sort( a + 1, a + n + 1, greater<I64>() ); // 最初からの総和を出す for( int i = 2; i <= n; i++ ){ a[i] += a[i-1]; } // インデックスを4分の1にしてって総和をだす I64 ans = 0; while( n > 0 ){ ans += a[n]; n /= 4; } cout << ans << endl; }