AGC018 C : Coins(800)
作成日：2017.07.25
最終更新日：2017.07.25
問題概要
$X+Y+Z$個の整数の組$(A_i,B_i,C_i)$がある。各組に対していずれか1つを選ぶ。
但し、$A,B,C$を選ぶのはそれぞれ$X,Y,Z$回である。
このとき、選んだ整数の総和の最大値を求めよ。
制約
$1 \leq X,Y,Z$
$X+Y+Z \leq 10^5$
$1 \leq A_i,B_i,C_i \leq 10^9$
考え方
問題を線形計画法と見ることができるから最小費用流問題として解きたくなるが、制約が大きいのでダメである。
とりあえず問題を簡単にするために、制約にはないが$Z=0$の時を考えてみる。
これは一旦すべての組で$B_i$を選ぶこととして、さらに$A_i-B_i$のうち$X$個をとると考えると貪欲法で解ける。
そこで、元の問題に戻った時になんとかして今考えた問題に帰着することを考える。
$A,B,C$の3つのものを2つにするためには、組たちを少なくとも2つに分ける必要がある。
2つに分けるとした時には、対称性より一方は$A$を、もう一方は$B$を考えないようにするとして良い。
これを達成するためには、$A$を選ばないようにした方で$A$を選ぶよりも、もう一方から$A$を選ぶ方が良いことを保証できれば良い。
ここで再び$A_i-B_i$を考えると、これが小さい組から$A$を、大きい組から$B$を選んだ時は選ぶものを逆にすることでより良い結果が得られることがわかる。
以上より組たちを$A_i-B_i$でソートした後ある箇所で2つに分割すれば、はじめに考えた問題に帰着できることがわかる。
但し、これを愚直にやると計算量は$O(n^2)$（但し$n=X+Y+Z$）かかってしまう。
そこで、まずは$A$を選ばないようにした方だけを組を追加していく順で計算し、次に$B$を選ばないようにした方だけで同じようにすれば、
priority_queueを用いれば計算量を$O(n \: log \: n)$に抑えることができる。
ソースコード
マクロ等はこちら
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;
}解法まとめ
$C_i$を引くことになるので、入力の時点で引いている。(16-18行)
$A_i-B_i$が大きい順にsortする。(21行)
priority_queueを用いて$[0,i]$から$A_i-C_i$が大きいものを$X$個選ぶ。(22-30行)
同様に$[i,n-1]$から$B_i-C_i$が大きいものを$Y$個選ぶ。(31-39行)
どこで区切ると良いかを計算する。(40-42行)