kmjp's blog

競技プログラミング参加記です

AtCoder ABC #160 : E - Red and Green Apples

Fの方が考えずにできたかも。
https://atcoder.jp/contests/abc160/tasks/abc160_e

問題

赤いリンゴA個、緑のリンゴB個、無色のリンゴC個がある。
それぞれのおいしさが与えられる。
無色のリンゴを赤か緑任意に塗ったのち、赤いリンゴをX個、緑のリンゴをY個選んだとき、おいしさの最大値を求めよ。

解法

リンゴのおいしさの小さい順に見て、「これを選ばないと必要な個数選べない」となったらそのリンゴを選ぼう。
A,B,Cは未処理のリンゴ数、X,Yは残りから選ばないといけないリンゴ数とする。

  • 今見ているリンゴが赤いとき、以下の条件で選ぶ。
    • これを選ばないと赤が足りなくなる(A+C==X)とき
    • これを選ばないと総数が足りなくなる(A+B+C==X+Y)とき
    • これを選ばないと緑が足りなくなるときで赤も余裕がないとき(A==XかつB+C==Y)とき
  • 緑の場合は、上記条件を赤と緑入れ替える。
  • 今見ているリンゴが無色の時、
    • これを選ばないと赤・緑・総数が足りなくなる時、余裕が比較的ある方に塗ったうえで選択する。
int X,Y,A,B,C;
vector<pair<int,int>> E;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>A>>B>>C;
	FOR(i,A) cin>>x, E.push_back({x,0});
	FOR(i,B) cin>>x, E.push_back({x,1});
	FOR(i,C) cin>>x, E.push_back({x,2});
	sort(ALL(E));
	
	ll ret=0;
	FORR(e,E) {
		x=e.second;
		y=e.first;
		if(x==0) {
			if(A+C==X || (B+C==Y&&A==X) || A+B+C==X+Y) {
				X--;
				ret+=y;
			}
			A--;
		}
		else if(x==1) {
			if((A+C==X&&B==Y) || B+C==Y || A+B+C==X+Y) {
				Y--;
				ret+=y;
			}
			B--;
		}
		else {
			if(A+C==X || B+C==Y || A+B+C==X+Y) {
				if(A<X) {
					X--;
				}
				else if(Y) {
					Y--;
				}
				ret+=y;
			}
			C--;
		}
	}
	cout<<ret<<endl;
}

まとめ

最初大きい順にやってしまい混乱した。