https://community.topcoder.com/stat?c=problem_statement&pm=15738

パラメタより生成される3つの数列A,B,Cがある（正式は問題文参照）。
以下の操作のいずれかを何度も行うことができる。

配列A,Bから要素を1つずつ消す。コストは(x + 消した要素の総和)
配列B,Cから要素を1つずつ消す。コストは(y + 消した要素の総和)
配列A,Cから要素を1つずつ消す。コストは(z + 消した要素の総和)

最適に要素を消して、残った数の総和を最小化せよ。
その上で、消すのにかかったコストも最小化せよ。

2≦A,B,Cの要素数≦10⁵
1≦x,y,z,ABCの要素≦10⁹　（ちょっと改変してるけど、問題ない）

解説

A,B,Cの要素数をa,b,cとする（問題でもそうだが）。
a+b+cが奇数であれば、必ず1つは残る。
どれを残すべきかは、3つを全て試して一番いいものを採用しよう。
doDeleteメソッドでは、それをやっていて、実際に解いているのは、solveメソッド。

まず、余ってしまうパターンを考えると、a,b,cの中で最大のものがそれ以外の和よりも大きい場合である。
その場合は、最大のものの一部が消化できない（なるべく小さい数を消化できないものとして残そう）。
a,b,cの中で最大のものがそれ以外の和と等しければ、最大のものとそれ以外でマッチングを行うことで全て消化できる。
a,b,cの中で最大のものがそれ以外の和より小さいならば、3種類の操作を1回ずつ行い、全部2個減らす。減らした段階で改めて、a,b,cの中で最大のものとそれ以外の和の大小関係を考えよう。

これで、残った数の総和の最小化は達成できた。
あとは消すのにかかったコストの最小化だが、結構難しい問題に見える。
消すのにかかるコストは残りの総和を最小化したときには一定になると仮定して、普通に計算する。
それで祈ってだすと通る。

struct DeleteArrays {
    pair<ll, ll> solve(vector<ll> A, vector<ll> B, vector<ll> C, ll x, ll y, ll z) {
        int a = A.size();
        int b = B.size();
        int c = C.size();
        ll ans1 = 0, ans2 = 0;

        int ma = max({ a, b, c });
        if ((a + b + c - ma) < ma) {
            int d = ma - (a + b + c - ma);
            if (max({ a, b, c }) == a) {
                rep(i, 0, d) ans1 += A[a - 1 - i];
                a -= d;
            }
            else if (max({ a, b, c }) == b) {
                rep(i, 0, d) ans1 += B[b - 1 - i];
                b -= d;
            }
            else if (max({ a, b, c }) == c) {
                rep(i, 0, d) ans1 += C[c - 1 - i];
                c -= d;
            }
        }

        rep(i, 0, a) ans2 += A[i];
        rep(i, 0, b) ans2 += B[i];
        rep(i, 0, c) ans2 += C[i];

        while ((a + b + c - max({ a, b, c })) > max({ a, b, c })) {
            ans2 += (x + y + z);
            a -= 2;
            b -= 2;
            c -= 2;
        }

        ma = max({ a, b, c });
        if (max({ a, b, c }) == a) {
            ans2 += x * b;
            ans2 += z * c;
        }
        else if (max({ a, b, c }) == b) {
            ans2 += x * a;
            ans2 += y * c;
        }
        else if (max({ a, b, c }) == c) {
            ans2 += y * b;
            ans2 += z * a;
        }

        return { ans1, ans2 };
    }
    vector<long long> doDelete(int a, int b, int c, long long x, long long y, long long z) {
        vector<ll> A(a), B(b), C(c);
        A[0] = 33; A[1] = 42;
        rep(i, 2, a) A[i] = ((5 * A[i - 1] + 7 * A[i - 2]) % 1000000007) + 1;
        B[0] = 13;
        rep(i, 1, b) B[i] = ((11 * B[i - 1]) % 1000000007) + 1;
        C[0] = 7; C[1] = 2;
        rep(i, 2, c) C[i] = ((5 * C[i - 1] + 7 * C[i - 2]) % 1000000007) + 1;
        sort(all(A), greater<ll>());
        sort(all(B), greater<ll>());
        sort(all(C), greater<ll>());

        pair<ll,ll> ans = { infl, infl };

        if ((a + b + c) % 2 == 1) {
            pair<ll,ll> cand;
            vector<ll> tmp;

            tmp = A;
            tmp.pop_back();
            cand = solve(tmp, B, C, x, y, z);
            cand.first += A[a - 1];
            chmin(ans, cand);

            tmp = B;
            tmp.pop_back();
            cand = solve(A, tmp, C, x, y, z);
            cand.first += B[b - 1];
            chmin(ans, cand);

            tmp = C;
            tmp.pop_back();
            cand = solve(A, B, tmp, x, y, z);
            cand.first += C[c - 1];
            chmin(ans, cand);
        }
        else ans = solve(A, B, C, x, y, z);

        return { ans.first, ans.second };
    }
};

はまやんはまやんはまやん

hamayanhamayan's blog

DeleteArrays [SRM 770 Div1 Easy / Div2 Hard]

解説