VK Cup 2015 - Round 3 F. Quest - すいバカ日誌

問題文

http://codeforces.com/contest/542/problem/F

解法

DPで解ける．
dp[i][j] := 高さ i に存在するノードが j 個であるようなときの，価値の最大値
とする．
ある高さ i のときに考えるべきタスクは，実はコストが T - i であるものだけでよい．
なぜならば，コスト i のタスクが仮に高さ T - i 以外のところにある場合，そのまま伸ばして高さ T - i のところまで持ってこれるし，そうしたほうが余裕が生まれるので伸ばさない理由がないためである．
遷移だが，仮に今の高さに j 個のノードがすでにあり，そこに k 個のタスクを追加することを考えると，一つ上の高さには最低限 (j + k + 1) / 2 個のノードが必要である．
また，このノードはタスクが置けないノードなので，できるだけ小さい方が良い．したがって，ちょうど (j + k + 1) / 2 個が最適である．故に遷移は
dp[i - 1][(j + k + 1) / 2] = max(dp[i - 1][(j + k + 1) / 2], dp[i][j] + sum[k])
となる．ただし sum[k] はその高さに対応するタスクのなかで価値が大きい方から k 個取ったときの総和である．
計算量は O(Tn^2) となる．

制約的にこれで十分だが，この問題は実は O(T + nlogn) で解ける．
高さ i で2つのタスク q1, q2 を使ったとすると，これはある意味高さ i - 1 で (q1 + q2) のタスクを使ったことと同じになることに注目する．
こうすることで，各高さではすべてのノードが葉であるとみなして解くことができる．
1つ上の高さにタスクを伝搬させる場合は，大きい方から2つずつ取っていって，それらの和を新たなタスクとすればよい（明らかにこれが最適）．
2個ずつ取っていくので log のオーダーで個数が小さくなり，この部分は O(nlogn) ，各高さで見ていくから O(T) で合わせて O(nlogn + T) となる．

ソースコード1

O(Tn^2) のほう．

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<int> t(n), q(n);
    vector<vector<int>> vs(T);
    for(int i = 0; i < n; ++i) {
        cin >> t[i] >> q[i];
        vs[T - t[i]].push_back(q[i]);
    }

    vector<vector<int>> dp(T, vector<int>(n + 1));
    if(!vs[0].empty()) {
        dp[0][1] = *max_element(begin(vs[0]), end(vs[0]));
    }
    for(int i = T - 1; i >= 1; --i) {
        sort(rbegin(vs[i]), rend(vs[i]));
        const int m = vs[i].size();
        vector<int> sum(m + 1);
        for(int j = 0; j < m; ++j) {
            sum[j + 1] = sum[j] + vs[i][j];
        }
        for(int j = 0; j <= n; ++j) {
            for(int k = 0; k <= m; ++k) {
                if((j + k + 1) / 2 > n) continue;
                dp[i - 1][(j + k + 1) / 2] = max(dp[i - 1][(j + k + 1) / 2], dp[i][j] + sum[k]);
            }
        }
    }

    cout << dp[0][1] << endl;
}

ソースコード2

O(T + nlogn) のほう．

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, T;
    cin >> n >> T;
    vector<vector<int>> ts(T);
    for(int i = 0; i < n; ++i) {
        int t, q;
        cin >> t >> q;
        ts[T - t].push_back(q);
    }

    for(int i = T - 1; i >= 1; --i) {
        if(ts[i].size() % 2 == 1) {
            ts[i].push_back(0);
        }
        sort(begin(ts[i]), end(ts[i]));
        const int m = ts[i].size();
        for(int j = 0; j < m / 2; ++j) {
            ts[i - 1].push_back(ts[i][2 * j] + ts[i][2 * j + 1]);
        }
    }

    cout << *max_element(begin(ts[0]), end(ts[0])) << endl;
}

感想

各ノードは葉であるか，必ず2つの子を持つ必要がある，と考えていてハマった（子は別に1つでいい）．