Good Bye 2015 E. New Year and Three Musketeers

問題

codeforces.com

解法

greedy に解くことが出来ます。

まず, a+b+c < x となる criminal さんがいたら勝てないので -1 を返すことになります。

それでなかったら, とりあえず a <= b <= c となるようにソートします。

multiset に 各 criminal さんの戦闘力を詰め込みます。
a+b+c 以外で勝てない criminal さんは a+b+c で応戦するしかないので, それで応戦しましょう。応戦したら, set からその人を取り除きます。
次に, b+c か a+b+c でしか勝てない criminal さんがいることがあります。ここで a+b+c を無駄に使うのは意味がない(だったら b+c で応戦して a が倒せるやつを探したほうが良い)ので b+c でこいつには応戦します。この時, a で応戦できる criminal さんがいたら a で倒します(set から b+c 以下の criminal 及び a 以下でなるべく戦闘力の大きい criminal を 取り除く)
次に大きいのは, a+c です。これも同様に greedy 出来て, set から a+c 以下の criminal さんを取り除きましょう。同時に b で処理できるなるべく戦闘力の高い criminal も取り除いておきます。

ここからが問題です。a+b と c の大小関係はよくわからないので, a+b 以下の criminal をいじってる間に c を頑張らせる, という戦略は必ずしも正しくありません。
しかし, わかることとして, 残りの時間は「a, b, c がそれぞれバラバラに criminal を倒す時間」と「a+b, c に分かれて criminal を倒させる時間」しか残ってないことがわかります。そこで, 「a, b, c がそれぞれバラバラに criminal を倒す時間」を何回使うかで場合分けして, その場合に「a+b, c に分かれて criminal を倒させる時間」が最小で何回になるかを数えたいと思います。

a+b, c に分かれる時, criminal を倒すのにかかる最小時間を求めることを考えます。
a+b で処理できる criminal の数を x, c で処理できる criminal の数を y とします。面倒なので, x >= y と仮定します。x <= y の場合もほとんど同じです。
x-y >= y であるとします。この時は, a+b しか処理できない x-y 人をやっつけている間に, c が処理すべき分は全部倒しきれるので, かかる時間は x-y です。
そうでない場合は, a+b しか処理できない criminal を倒した後も, まだ 2*y-x 人だけ criminal は残っています。残った criminal は a+b でも c でも処理できるので, (2*y-x+1)/2 時間で残りも処理できます。よって, かかる時間は x-y+(2*x-y+1)/2 です。

int m[3], ans = 0;

// least 以上だったら破壊する
// その際 extra 未満の数があったらそいつも破壊
void calc(int least, int extra, multiset<int>& S) {
    while (!S.empty()) {
        auto it = S.end();
        --it;
        if (*it < least) break;
        ans++;
        S.erase(it);
        it = S.lower_bound(extra);
        if (it != S.begin()) it--;
        if (*it < extra) S.erase(it);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < 3; i++) cin >> m[i];
    sort(m, m+3);
    multiset<int> criminal;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        criminal.insert(x-1);
    }
    {
        auto it = criminal.end();
        it--;
        if (*it >= m[0]+m[1]+m[2]) {
            cout << -1 << endl;
            return 0;
        }
    }
    calc(m[1]+m[2], -1, criminal);
    calc(m[0]+m[2], m[0], criminal);
    calc(max(m[2], m[0]+m[1]), m[1], criminal);
    int x = 0, y = 0;
    for (int el : criminal) {
        if (el < m[0]+m[1]) x++;
        if (el < m[2]) y++;
    }
    int best = 1e9;
    for (int i = 0; i <= n; i++) {
        {
            int z = max(x, y);
            int w = min(x, y);
            if (z-w >= w) best = min(best, i+z-w);
            else best = min(best, i+(z-w)+(2*w-z+1)/2);
        }
        for (int j = 0; j < 3; j++) {
            if (criminal.empty()) break;
            auto it = criminal.lower_bound(m[j]);
            if (it != criminal.begin()) it--;
            if (*it < m[j]) {
                if (*it < m[0]+m[1]) x--;
                if (*it < m[2]) y--;
                criminal.erase(it);
            }
        }
    }
    cout << ans+best << endl;
    return 0;
}