2012 TCO Algorithm Round 2B med: HeavyBooks

本が 10^6 グラムってそれ 1 トンやんけ！

問題

TopCoder Statistics - Problem Statement

解法

Tomek 君が最初に押し付ける本を決めたら, 後は両者とも, 貪欲に「できるだけ重い本を相手に押し付ける」というのが最適です。そうしないと, 余計に重い本を相手から押し付けられてしまうからです。

ということで, 選ぶべき本のリストを決めたら両者が持っている本のリストが決定します。本のリストを 0, 1, 2, ..., moves[0]-1 として, 本の分布がどのようになっているかをメモしておきましょう。

あとは, Tomek にとって最適になる(pair(W-T, W+T) を最大化)ように dp をします。

dp[i][j] = (本の i 番目までで, 2 人が持っている本のうち j 冊の本が使われる時の, Tomek にとっての最適ペア) で上手く dp しましょう。

const int INF = 1e9;

pair<int, int> dp[55][55];
int isInT[55];

class HeavyBooks {
public:
    vector <int> findWeight(vector <int> books, vector <int> moves) {
        int n = books.size(), m = moves.size();
        vector<int> t(moves[0]), w;
        for (int i = 0; i < moves[0]; i++) t[i] = i;
        for (int i = 0; i < m; i++) {
            if (i%2 == 0) {
                int size = min<int>(moves[i], t.size());
                sort(t.begin(), t.end());
                for (int j = 0; j < size; j++) {
                    w.push_back(t.back());
                    t.pop_back();
                }
            } else {
                int size = min<int>(moves[i], w.size());
                sort(w.begin(), w.end());
                for (int j = 0; j < size; j++) {
                    t.push_back(w.back());
                    w.pop_back();
                }
            }
        }
        sort(books.begin(), books.end());
        for (int i = 0; i < moves[0]; i++) {
            if (find(t.begin(), t.end(), i) != t.end()) isInT[i] = 1;
            else isInT[i] = 0;
        }
        for (int i = 0; i < 55; i++) for (int j = 0; j < 55; j++) {
            dp[i][j] = pii(INF, -INF);
        }
        for (int i = 0; i < 55; i++) dp[i][0] = pii(0, 0);
        for (int i = 1; i <= n; i++) for (int j = 1; j <= moves[0]; j++) {
            auto& p = dp[i][j];
            auto q = dp[i-1][j];
            if (p.second-p.first < q.second-q.first || (p.second-p.first == q.second-q.first && p.first+p.second < q.first+q.second)) {
                p = q;
            }
            auto r = dp[i-1][j-1];
            if (isInT[j-1]) {
                r.first += books[i-1];
            } else {
                r.second += books[i-1];
            }
            if (p.second-p.first < r.second-r.first || (p.second-p.first == r.second-r.first && p.first+p.second < r.first+r.second)) {
                p = r;
            }
        }
        vector<int> ret;
        ret.push_back(dp[n][moves[0]].first);
        ret.push_back(dp[n][moves[0]].second);
        return ret;
    }
};