Mister雑記

競プロやります。

AGC018-C 「Coins」 (800)

最初の最初で詰まると哀しいよね。

問題リンク

概要

 X + Y + Z人の人がいて、各々金、銀、銅のコインをそれぞれ A_i枚、 B_i枚、 C_i枚持っている。

あなたは彼らのうち X人から金のコイン、 Y人から銀のコイン、 Z人から銅のコインを全て貰うことができる。ただし同じ人から2種類以上のコインを貰うことはできない。

このとき、あなたが貰えるコインの枚数の最大値を求めよ。

制約

  •  1 \leq X, Y, Z
  •  X + Y + Z \leq 10^5
  •  1 \leq A_i, B_i, C_i \leq 10^9

解説

銅は無視して金と銀についてだけ考えることにする。 あと冗長なので金のコインを貰う人のことを「金の人」と呼ぶことにする。銀と銅も同様。

まず、人々を(金の枚数)-(銀の枚数)で昇順にソートして左から並べる。 この中には最適解における金の人 X人と銀の人 Y人がいるわけだが、実は最適解における金の人はすべての銀の人より右側にいることが分かる。

これは背理法で示すことができる。仮に金の人の右に銀の人がいると仮定しよう。このとき、この2人から貰うコインの種類を交換することで、先程のソートの前提から貰える総コインはより多くなる。元金の人から銀コインを貰うことによる損を、元銀の人から金コインを貰うことによる得が上回るのだ。

ここまで来たらゴールは近い。先のソートした状態にて、左から K人と右から X + Y + Z - K人の2グループに分ける。このとき先の定理?から、

  • 左グループは Y人を銀の人、 K - Y人を銅の人
  • 右グループは X人を金の人、 Y + Z - K人を銅の人

に分けるような最適解が存在する。各グループにおける割り振りはどうすればいいかというと、先と同じように(金/銀の枚数)-(銅の枚数)でソートしてやればいい。この辺はグループの人数を増やしながらpriority_queueを使えばできる。

この割り振りにおけるコインの合計枚数を各 Kについて求めれば、その最大値が答えとなる。

類題の話

この問題を解いてる途中「なんか似たような問題なかったっけ?」と思い、過去問を漁ったら下位問題に相当するものがあった。それがARC074-D「3N Numbers」(500)である。最初の「金の人と銀の人が交わらない」ということに気づくと、後は実装の手間が加わっただけのほぼ同型問題になってしまう。

これを解いた経験もあって、大枠の実装自体は比較的スムーズに進んだ(細かい部分で相当つまづいたが)。こういうところでも精進の成果が現れるものだ。

実装例

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;

#define mp make_pair
#define SORT(v) sort((v).begin(), (v).end())
#define GSORT(v) sort((v).begin(), (v).end(), greater<decltype((v).front())>())
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)

int main() {
    // X, Y, Zを受け取る
    // N = X + Y + Z
    ll X[3], N = 0;
    FOR(j, 0, 3) {
        cin >> X[j];
        N += X[j];
    }

    // A_i, B_i, C_iを受け取る
    vector<vector<ll>> coin(N, vector<ll>(3, 0));
    FOR(i, 0, N) {
        FOR(j, 0, 3) {
            cin >> coin[i][j];
        }
    }

    // (gold - silver, index)の配列
    vector<pair<ll, ll>> gs(N);
    FOR(i, 0, N) {
        gs[i] = make_pair(coin[i][0] - coin[i][1], i);
    }

    SORT(gs);

    // silver[i] = 「K = Y + iにおける左グループのコイン枚数の最大値」
    vector<ll> silver(X[2] + 1, 0);
    
    // 中身は(silver - bronze, index)
    GPQ<pair<ll, ll>> sb;
    
    // まずは最初のY個を追加してしまう
    FOR(i, 0, X[1]) {
        ll id = gs[i].second;
        sb.push(make_pair(coin[id][1] - coin[id][2], id));
        silver[0] += coin[id][1];
    }

    // ここから銅の人が出始める
    FOR(i, 0, X[2]) {
        ll id = gs[i + X[1]].second;
        sb.push(mp(coin[id][1] - coin[id][2], id));

        silver[i + 1] = silver[i] + coin[id][1];

        // 先頭の人を銀の人から銅の人に変える
        auto p = sb.top();
        sb.pop();
        silver[i + 1] += (coin[p.second][2] - coin[p.second][1]);
    }

    // 逆順にして(gold - bronze)で全く同じことをする
    GSORT(gs);

    vector<ll> gold(X[2] + 1, 0);
    GPQ<pair<ll, ll>> gb;
    FOR(i, 0, X[0]) {
        ll id = gs[i].second;
        gb.push(mp(coin[id][0] - coin[id][2], id));
        gold[0] += coin[id][0];
    }

    FOR(i, 0, X[2]) {
        ll id = gs[i + X[0]].second;
        gb.push(mp(coin[id][0] - coin[id][2], id));

        gold[i + 1] = gold[i] + coin[id][0];

        auto p = gb.top();
        gb.pop();
        gold[i + 1] += (coin[p.second][2] - coin[p.second][0]);
    }

    ll ans = 0;
    FOR(i, 0, X[2] + 1) {
        // K = Y + iにおけるコインの合計枚数と比較
        ans = max(ans, silver[i] + gold[X[2] - i]);
    }

    cout << ans << endl;
    return 0;
}

感想

  • 最初の一歩はどうやったら踏み出せるようになるんだろうか。
    • それ以降は自力でできたのは良かった。
  • 変数名にセンスのNASAが露呈している。
  • 手間を惜しまず実装の情報を紙に書こう。