kmjp's blog

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

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

普段のABCよりはだいぶ難しかった。
https://atcoder.jp/contests/aising2020/tasks/aising2020_e

問題

N頭のラクダを順に並べるとする。
各ラクダiは、先頭からK[i]番目以内にいるとL[i]、それ以降だとR[i]のうれしさを得る。
任意の順で並べたとき、うれしさの最大値を求めよ。

解法

L[i]がR[i]以上であるものは前、そうでないものは後ろに寄せた方がよい。
まずラクダをその2種に分け、それぞれ考える。

前者については、L[i]-R[i]が大きいもの程優先的にK[i]以前に配置するようにするのが良い。
そこで、K[i]以前に空きがあれば、そのうちできるだけ後ろに配置しよう。
前に配置すると、他に前に配置したいものを邪魔してしまう。
K[i]以前に空きがなければできるだけ後ろに寄せる。

L[i]よりR[i]が大きい場合も同様。できるだけK[i]直後に置くようにしよう。

int T;
int N;
int K[202020],L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ret=0;
		vector<pair<int,int>> A,B;
		set<int> AS,BS;
		FOR(i,N) {
			cin>>K[i]>>L[i]>>R[i];
			
			if(L[i]>=R[i]) {
				ret+=R[i];
				A.push_back({L[i]-R[i],K[i]});
			}
			else {
				ret+=L[i];
				B.push_back({R[i]-L[i],K[i]});
			}
		}
		FOR(i,A.size()) AS.insert(i);
		FOR(i,B.size()) BS.insert(A.size()+i);
		sort(ALL(A));
		reverse(ALL(A));
		
		FORR(v,A) {
			auto it=AS.lower_bound(v.second);
			if(it==AS.begin()) {
				AS.erase(*AS.rbegin());
			}
			else {
				it--;
				ret+=v.first;
				AS.erase(it);
			}
		}
		sort(ALL(B));
		reverse(ALL(B));
		FORR(v,B) {
			auto it=BS.lower_bound(v.second);
			if(it==BS.end()) {
				BS.erase(BS.begin());
			}
			else {
				ret+=v.first;
				BS.erase(it);
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

普段のABCのFぐらいありそう。