CodeQUEEN 2024 決勝 : H - Good bye, AtCoder Land.

これ系いつも初手迷うんだよな。
https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_h

問題

N個のアトラクションがある。
i番のアトラクションは、普通に乗るとA[i]分かかり、ファストパスを使うとB[i]分かかる。

同じアトラクションには複数回乗れない。
また、ファストパスをK枚まで使えるとき、T分で最大何個のアトラクションに乗れるか。

解法

K個以下の場合、全部ファストパスを使えばよいので、Bのうち小さい順にK個まで選び、T分を超えないか判定しよう。
もしK個を超えて乗れる場合を考える。
ファストパスを使うなら、A[i]-B[i]が大きい順に候補となる。
そこで、まずアトラクションをA[i]-B[i]順にソートしよう。

そのうえで二分探索で解く。
仮にv個アトラクションを乗れるかを考える。

• 先頭a個のアトラクションのうち、B[i]の小さなK個に乗る。
• 末尾(N-a)個のアトラクションのうち、A[i]の小さな(v-K)個に乗る。

と考え、aを走査しながら、上記の和を更新し、T以下のタイミングがあるか判定しよう。

int N,K;
ll T,A[202020],B[202020];
pair<ll,ll> P[202020];

ll ok(int v) {
	if(v>N) return T+1;
	
	ll S=0;
	multiset<ll> Q1,Q2,Q3;
	int i;
	FOR(i,K) {
		S+=B[i];
		Q1.insert(B[i]);
	}
	FOR(i,N-K) {
		Q3.insert(A[i+K]);
	}
	Q3.insert(1LL<<60);
	FOR(i,v-K) {
		ll a=*Q3.begin();
		Q3.erase(Q3.begin());
		Q2.insert(a);
		S+=a;
	}
	if(S<=T) return S;
	for(i=K;i<N;i++) {
		ll a=A[i];
		if(Q2.count(a)) {
			Q2.erase(Q2.find(a));
			S-=a;
			ll b=*Q3.begin();
			S+=b;
			if(b>=1LL<<60) return T+1;
			Q3.erase(Q3.begin());
			Q2.insert(b);
		}
		else {
			assert(Q3.count(a));
			Q3.erase(Q3.find(a));
		}
		ll b=B[i];
		if(b<*Q1.rbegin()) {
			S-=*Q1.rbegin();
			Q1.erase(Q1.find(*Q1.rbegin()));
			S+=b;
			Q1.insert(b);
		}
		if(S<=T) return S;
	}
	return T+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>T;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		P[i]={-(A[i]-B[i]),A[i]};
	}
	sort(P,P+N);
	vector<ll> V;
	FOR(i,N) {
		A[i]=P[i].second;
		B[i]=P[i].first+P[i].second;
		V.push_back(B[i]);
	}
	// K以下？
	sort(ALL(V));
	ll sum=0;
	int num=0;
	FOR(i,N) {
		sum+=V[i];
		if(sum<=T) num++;
	}
	if(num<=K) {
		cout<<num<<endl;
		return;
	}
	int ret=K;
	for(i=20;i>=0;i--) if(ok(ret+(1<<i))<=T) ret+=1LL<<i;
	cout<<ret<<endl;
	
}

まとめ

今回AtCoder Landがやたら出てくるけど、問題名が何かのネタ？