Codeforces ECR #117 : E. Messages

不参加だった回。
https://codeforces.com/contest/1612/problem/E

問題

N人の学生がおり、それぞれ読みたいメッセージの種類M[i]と、読んでくれるメッセージ数K[i]が与えられる。

今T個のメッセージを展開したとする。
T≦K[i]なら、その学生はメッセージをすべて読み、その中にM[i]が含まれていると満足する。
T＞K[i]なら、その学生はメッセージをランダムでK[i]個だけ読み、その中にM[i]が含まれていると満足する。

満足する学生数の期待値を最大化するために、展開するメッセージを求めよ。

解法

メッセージ数Tは高々max(K)まで調べればよい。
メッセージ数Tを総当たりし、その際種類ごとに読んでくれる学生数の期待値を求めよう。
上位T種類のメッセージを展開することにしたとき、その期待値が最大となる構成を答える。

int N;
vector<int> C[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		C[x].push_back(y);
	}
	double ma=0;
	vector<int> ret;
	for(k=1;k<=20;k++) {
		vector<pair<double,int>> V;
		for(i=1;i<=200000;i++) {
			double a=0;
			FORR(c,C[i]) {
				a+=1.0*min(c,k)/k;
			}
			V.push_back({a,i});
		}
		sort(ALL(V));
		reverse(ALL(V));
		double s=0;
		FOR(i,k) s+=V[i].first;
		if(s>ma) {
			ma=s;
			ret.clear();
			FOR(i,k) ret.push_back(V[i].second);
			sort(ALL(ret));
		}
		
	}
	
	cout<<ret.size()<<endl;
	FORR(r,ret) cout<<r<<" ";
}

まとめ

問題文もう少し短くならないかな…。