AtCoder ARC #186 (AtCoder Japan Open -予選-) : C - Ball and Box

これもまぁすんなり解けて良かった。
https://atcoder.jp/contests/arc186/tasks/arc186_c

問題

M種類のボールが、それぞれ大量にある。
またN個の箱があり、i個めの箱は容量がボールV[i]個分、価格がP[i]である。

ここで2人で以下のゲームを行う。

• 先手がいずれかのボールを選び、後手に渡す
• 後手は、手持ちの箱のうちどこかにそのボールを入れる。その際、初期状態では後手は箱を持たないが、任意のタイミングでP[i]を払い箱を入手できる。
  • なお、1つの箱には1種類のボールしか入れられない。
  • ボールを無事箱に入れると、後手は1のお金を得る。
  • ボールを入れられない場合、その場でゲーム終了。

先手は後手のお金を最小にしようとしてボールを選び、後手は最大にしようとして箱やボールを入れる先を選ぶ。
後手の利益はいくらか。

解法

V[i]≦P[i]の箱は、後手は持っても得しないので無視しよう。
最後の状態を考えると、後手はM個の箱を持っており、一番容量の小さい箱は埋まって、残り(M-1)個は1個ずつ入った状態となる。
先手は、当然容量の多い(M-1)箱を無駄にさせようとしてくる。

よって、容量の小さい順にT個は中が埋まるまでボールを詰めるとし、残り(N-T)個の箱のうち(M-1)個価格が安いものを選ぶ、という戦略が考えられる。
Tを大きい順に走査しながら、残り(N-T)個の箱のうち(M-1)個の価格の最安値を求めて行けばよい。

int T;
int N,M;
pair<int,int> X[303030];
ll S[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>X[i].first>>X[i].second;
			if(X[i].first<=X[i].second) {
				N--;
				i--;
			}
		}
		
		if(N<M) {
			cout<<0<<endl;
			continue;
		}
		
		sort(X,X+N);
		FOR(i,N) S[i+1]=S[i]+X[i].first-X[i].second;
		ll ret=0;
		multiset<ll> V;
		ll mp=0;
		FOR(i,M-1) {
			V.insert({1LL<<60});
		}
		
		if(M==1) ret=S[N];
		
		for(i=N-1;i>=0;i--) {
			x=X[i].second;
			mp+=x;
			V.insert(x);
			ll a=*V.rbegin();
			if(a!=1LL<<60) mp-=a;
			V.erase(V.find(a));
			if(V.empty()||*V.rbegin()!=1LL<<60) ret=max(ret,S[i]-mp+M-1);
			
		}
		cout<<ret<<endl;
	}
}

まとめ

コーナーケースのワンミスがもったいない。