kmjp's blog

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

CODE FESTIVAL 2018 Final: F - Dinner Planning

これも考察が済むと実装は軽い。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_f

問題

N日間の予定が与えられる。
各日、ラーメン屋とレストランどちらで食事をとるかと、食事をとった場合に得られる満足度が与えられる。

パラメータとしてグルメ度がある。初期値は0で、0~Kの間を取ることができる。
食事をラーメン屋でとるとグルメ度が-1、レストランでとると+1変化する。

各日、食事をとるかとらないか任意に選べる場合、グルメ度の条件を満たしたまま得られる満足度の総和の最大値を求めよ。

解法

後でキャンセルできるラーメン屋およびレストランの満足度のmultisetを管理しよう。
満足度xの場合、ラーメン屋は(K-x)個、レストランはx個の満足度を持つ状態となる。
(初期値ではラーメン屋側がK個の∞の値を入れたmultisetを持つことにする)

各日においてラーメン屋に行く場合、まずは必ずその日ラーメンを食べることにして解に満足度を加算すると同時に、ラーメン屋側のmultisetにその満足度を加える。
逆にレストランは1個要素を減らすことにする。multisetには「あとでキャンセルするかもしれない要素」を残すので、当然満足度が高い日はキャンセルさせたくないので、最大値の物を取り除く。
ただしラーメン屋のmultisetが(K+1)個になってしまう場合、最小値を1個取り除くと同時に、解からその分減算しよう。
すなわち過去にさかのぼり満足度最低の物をキャンセルしたとみなす。

レストランに行く場合も同様。

int N,K;
multiset<ll> A,B;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) A.insert(1LL<<60);
	FOR(i,N) {
		cin>>x>>y;
		ret+=y;
		if(x==0) {
			A.insert(y);
			if(B.size()) {
				B.erase(B.find(*B.rbegin()));
			}
			else {
				ret-=*A.begin();
				A.erase(A.begin());
			}
		}
		else {
			B.insert(y);
			if(A.size()) {
				A.erase(A.find(*A.rbegin()));
			}
			else {
				ret-=*B.begin();
				B.erase(B.begin());
			}
		}
		
	}
	cout<<ret<<endl;
}

まとめ

本番の緊張した状態だとややこしい実装しちゃいそう。