Codeforces #339 Div1. B. Skills

うーん、面倒なだけで余り面白みはない問題だな…。
http://codeforces.com/contest/613/problem/B

問題

プレイヤーはN種のスキルを持ち、各初期パラメータはa[i]である。
プレイヤーは各パラメータを最大で合計Mだけ(整数単位で)増加できる。ただし上限はAである。

プレイヤーの強さは以下の和である。

• CF * (上限Aに達したスキル数)
• CM * (パラメータの最小値)

プレイヤーが最適にパラメータ増加を行った場合、到達できる強さの最大値を答えよ。

解法

全パラメータを上限に到達させられるなら、CF*N + CM*Aが解となる。

それ以外の場合、尺取法の要領で解く。

パラメータを少ないコストで上限に到達させるには、当然ながら元々高いパラメータを上げていく方が効率が良い。
そこでスキルを初期パラメータ値でソートしよう。
パラメータ上位をいくつ上限に到達させたとき、残りの増加可能パラメータを用いて他のスキルを底上げし、最小値をどこまで上げられるか求める。
これは事前に累積和を計算しておくと、尺取法の要領で求められる。

ll N,AA,CF,CM,M;
pair<ll,int> A[101010];
ll S[101010];
int R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>AA>>CF>>CM>>M;
	FOR(i,N) cin>>A[i].first, A[i].second=i;
	
	sort(A,A+N);
	FOR(i,N) S[i+1]=S[i]+A[i].first;
	
	int mi=0,ma=0;
	ll lvv=0;
	ll V=0;
	if(N*AA-S[N]<=M) {
		V=N*CF+AA*CM;
		mi=0,ma=N;
	}
	else {
		y=N;
		for(x=N;x>=0;x--) {
			if(x<N) {
				M-=AA-A[x].first;
				if(M<0) break;
			}
			while(y*A[y-1].first-S[y]>M) y--;
			y=min(y,x);
			ll left=M-(y*A[y-1].first-S[y]);
			ll lv=min(A[y-1].first+left/y,AA);
			ll sc=(N-x)*CF+lv*CM;
			if(sc>V) {
				V=sc;
				mi=y;
				ma=N-x;
				lvv=lv;
			}
		}
	}
	
	cout<<V<<endl;
	FOR(i,N)  R[A[i].second]=A[i].first;
	FOR(i,mi) R[A[i].second]=lvv;
	FOR(i,ma) R[A[N-1-i].second]=AA;
	FOR(i,N) {
		cout<<R[i];
		if(i<N-1) cout<<" ";
	}
	cout<<endl;
}

まとめ

ちょっと無理くり作った問題設定みたいで余り好きじゃないな…。