Codeforces Round #186 (Div. 2) C. Ilya and Matrix

,

sortして順位で重み付けながら足し合わせる。

C. Ilya and Matrix

解法

与えられた数列の中で、$1$番目に大きい数は$n+1$倍、$2 \dots 4$番目に大きい数は$n$倍、$5 \dots 16$番目に大きい数は$n-1$倍、という風に重み付けて総和を取ればよい。

指示された手順を見ると、ある$1$つの数は$n+1$回使われ、ある$3$つの数は$n$回使われ、ある$12$つの数は$n-1$回使われ、となっていることが分かる。 何度も使う数の選択の基準はその数の大きさと配置であるが、周囲と比較して最も大きいものが採用されること、好きに配置してよいことから、上記のように最適に総和を取ることができる。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n; n = log2(n)/2;
    vector<ll> a(1<<2*n); repeat (i,1<<2*n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    ll result = 0;
    repeat (i,1<<2*n) {
        result += a[i] * (n - int(ceil(log2(i+1)/2)) + 1);
    }
    cout << result << endl;
    return 0;
}