AtCoder ABC #143 : F - Distinct Numbers

意外とコード短い。
https://atcoder.jp/contests/abc143/tasks/abc143_f

問題

N枚のカードがあり、それぞれ整数が記入されている。
1回で、ここからK枚を取り除くことを考える。
ただし取り除くK枚は書かれた整数が異なっていなければならない。

K=1～Nに対し、それぞれ何回K枚取り除けるか答えよ。

解法

m回取り除ける最大のKを求めることを考えよう。
整数xが書かれたカードの枚数をC[x]とする。
m回取り除くということは各整数をm回まで取り除く対象にできる。
よってsum(min(m,C[x]))/m回が最大となる。

mをN→1と降順に見ていくと、sum(min(m,C[x]))はC[x]がm以下のものの総和と、m以上の種類数を分けて考えれば均しでO(N)で処理できる。

int N;
int A[303030];
int ma[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,int> M;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}
	vector<int> V;
	FORR(m,M) V.push_back(m.second);
	sort(ALL(V));
	int over=0;
	ll sum=N;
	for(i=N;i>=1;i--) {
		
		ll tot=1LL*over*i+sum;
		ma[tot/i]=max(ma[tot/i],i);
		
		while(V.size() && V.back()>=i) {
			sum-=V.back();
			V.pop_back();
			over++;
		}
	}
	for(i=N;i>=1;i--) ma[i]=max(ma[i],ma[i+1]);
	FOR(i,N) cout<<ma[i+1]<<endl;
	
	
	
}

まとめ

最近400ptまでがだいぶ簡単だね。