Codeforces ECR #182 : D. Price Tags

自然なようで変な問題設定だな。
https://codeforces.com/contest/2144/problem/D

問題

整数列Aと正整数Yが与えられる。
2以上の正整数Xを選ぶと、Aの各値はXで割って余りを切り上げた値になる。
その際、処理前のAと処理後のAを多重集合と見たとき、差の要素数1個当たりYのコストがかかる。

処理後のAの総和からコストを引いたものの最大値を求めよ。

解法

f(n) := Aのうちn以下の値の要素数
g(n) := Aのうちn以下の値の要素の総和
としたとき、Xを2～max(A)まで総当たりしつつ、かかるコストを計算していこう。

int T,N;
ll Y,C[202020];
int NC[202020];
int NS[202020];
ll ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Y;
		ZERO(NC);
		ZERO(ret);
		FOR(i,N) {
			cin>>C[i];
			NC[C[i]]++;
		}
		sort(C,C+N);
		for(i=1;i<=200000;i++) NS[i]=NS[i-1]+NC[i];
		for(i=1;i<=200000;i++) {
			for(j=1;(j-1)*i<=200000;j++) {
				ret[i]+=1LL*j*(NS[min(200000,j*i)]-NS[i*(j-1)]);
				ret[i]+=1LL*min(NC[j],(NS[min(200000,j*i)]-NS[i*(j-1)]))*Y;
			}
		}
		ll ma=-1LL<<60;
		
		for(i=2;i<=200000;i++) ma=max(ma,ret[i]);
		cout<<ma-1LL*N*Y<<endl;
		
	}
}

まとめ

意外にコード量は短い。