エイシング プログラミング コンテスト 2020 E - Camel Train

• コンテスト参加記はこちら coonevo.hatenablog.com

問題へのリンク

解説

• どう置いても必ず得られるベース得点がある
• ベース得点を先に考慮すると、あるラクダについて左右の好みと得点という2つのパラメータのみを考えるだけでよくなる
• 左右の好みが混ざっていたら、それを解消することで損をすることはないので、左右独立に解けばよい

• 左について以下のような貪欲法を適用する(右については反転して同様)

  • 使える候補の集合を持つ(最初は空集合)
  • 以下をindexが大きい順に繰り返す
    • ある位置について、のラクダをに追加する
    • が空でない場合、の中で得点が最大のラクダを位置に割り当てることにし、から最大のラクダを削除する

• 大きい方から進めるのは、右で追加された未使用のラクダは左で使えるという性質...(1)があるからである

• この処理では一見左右で独立に解いた割り当てがバッティングするように思われるが、例えば左の場合で解いた割り当てを左詰めにし直す（右も同様）という処理を最後に加えれば、バッティングすることはない。
• 左詰めにしても問題ないのは、性質(1)を考えればわかる

実装

左右で実装を変えてもよいが、構造が同じ問題を逆向きに解くだけなので、indexを逆順に変えれば全く同じコードで計算できる。

• 提出へのリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;

using P = pair<int, ll>;
int N;

ll calc(vector<P> &v){
    sort(all(v));
    int sz = v.size();
    ll res = 0;
    priority_queue<ll> pq;
    int idx = sz-1;
    for(int i = N - 1; i >= 0; i--){
        while(idx >= 0 && v[idx].first == i){
            pq.push(v[idx].second);
            idx--;
        }
        if(pq.empty())continue;
        res += pq.top();
        pq.pop();
    }
    return res;
}

void solve(){
    cin >> N;
    vector<P> lefts, rights;
    ll base = 0; // 必ずもらえる点数
    rep(i,N){
        int K;
        ll L, R;
        cin >> K >> L >> R;
        K--;
        ll minn = min(L, R);
        base += minn;
        L -= minn;
        R -= minn;
        // {0,0}
        if(L == R)continue;
        // {X,0}
        if(L > R)lefts.emplace_back(K, L);
        // {0,X}
        if(L < R){
            K++;
            // 同じcalc functionで計算するためにidxを逆順に入れかえる
            rights.emplace_back(N-1-K, R);
        }
    }
    cout << base + calc(lefts) + calc(rights) << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)solve();
}