AGC018 C : Coins(800)
作成日：2017.07.25
最終更新日：2017.07.25
問題概要
X+Y+Z個の整数の組(Ai,Bi,Ci)がある。各組に対していずれか1つを選ぶ。
但し、A,B,Cを選ぶのはそれぞれX,Y,Z回である。
このとき、選んだ整数の総和の最大値を求めよ。
制約
1≤X,Y,Z
X+Y+Z≤105
1≤Ai,Bi,Ci≤109
考え方
問題を線形計画法と見ることができるから最小費用流問題として解きたくなるが、制約が大きいのでダメである。
とりあえず問題を簡単にするために、制約にはないがZ=0の時を考えてみる。
これは一旦すべての組でBiを選ぶこととして、さらにAi−BiのうちX個をとると考えると貪欲法で解ける。
そこで、元の問題に戻った時になんとかして今考えた問題に帰着することを考える。
A,B,Cの3つのものを2つにするためには、組たちを少なくとも2つに分ける必要がある。
2つに分けるとした時には、対称性より一方はAを、もう一方はBを考えないようにするとして良い。
これを達成するためには、Aを選ばないようにした方でAを選ぶよりも、もう一方からAを選ぶ方が良いことを保証できれば良い。
ここで再びAi−Biを考えると、これが小さい組からAを、大きい組からBを選んだ時は選ぶものを逆にすることでより良い結果が得られることがわかる。
以上より組たちをAi−Biでソートした後ある箇所で2つに分割すれば、はじめに考えた問題に帰着できることがわかる。
但し、これを愚直にやると計算量はO(n2)（但しn=X+Y+Z）かかってしまう。
そこで、まずはAを選ばないようにした方だけを組を追加していく順で計算し、次にBを選ばないようにした方だけで同じようにすれば、
priority_queueを用いれば計算量をO(nlogn)に抑えることができる。
ソースコード
マクロ等はこちら
- const int MC = 100010;
- const LL INF = 1234567890123456;
- int X,Y,Z;
- int n; //n=X+Y+Z
- int A[MC],B[MC],C[MC];
- int s[MC]; //A-Bでsortしたときの順
- priority_queue<int , vector<int> , greater<int> > QA,QB;
- LL mA[MC] , mB[MC]; //QAとmAは22-30行,QBとmBは31-39行参照
- LL ans , mx = -INF; //mxは41行参照
-
- int main(){
- scanf("%d%d%d" , &X , &Y , &Z);
- n = X+Y+Z;
- repp(i,0,n){
- scanf("%d%d%d" , A + i , B + i , C + i);
- A[i] -= C[i];
- B[i] -= C[i];
- ans += C[i];
- s[i] = i;
- }
- sort(s,s+n,[&](const int p , const int q){return A[p]-B[p]>A[q]-B[q];});
- repp(i,0,X){
- QA.push(A[s[i]]);
- mA[X-1] += A[s[i]];
- }
- repp(i,X,n-Y){
- QA.push(A[s[i]]);
- mA[i] = mA[i-1] + A[s[i]] - QA.top();
- QA.pop();
- }
- repm(i,n-1,n-Y-1){
- QB.push(B[s[i]]);
- mB[n-Y] += B[s[i]];
- }
- repm(i,n-Y-1,X-1){
- QB.push(B[s[i]]);
- mB[i] = mB[i+1] + B[s[i]] - QB.top();
- QB.pop();
- }
- repp(i,X-1,n-Y){
- mx = max(mx , mA[i]+mB[i+1]);
- }
- printf("%lld\n" , ans + mx);
- return 0;
- }
解法まとめ
Ciを引くことになるので、入力の時点で引いている。(16-18行)
Ai−Biが大きい順にsortする。(21行)
priority_queueを用いて[0,i]からAi−Ciが大きいものをX個選ぶ。(22-30行)
同様に[i,n−1]からBi−Ciが大きいものをY個選ぶ。(31-39行)
どこで区切ると良いかを計算する。(40-42行)