ABC143 F - Distinct Numbers - ferinの競プロ帳

基本的に使用している文字は公式解説と同じ意味になるように使っています．
$X$ 回操作ができるような整数 $K$ のうち最大のものを $f(X)$ とする．

$C_i$ を数列 $A$ に含まれる $i$ の個数とする． $X$ 回操作するとき，整数 $i$ を選択できる回数は $\min(C_i, X)$ 回である．よって $X$ 回操作をするときに，操作の対象にできるカードは $\sum_{i=1}^{N} \min(C_i, X)$ 枚である．したがって $f(X)=\lfloor \sum_{i=1}^{N} \min(C_i, X) / X \rfloor$ となる．

$C_i$ をソートしておくと $C_i > X$ となるような最小の $i$ を二分探索で求めることができる．このような $i$ を $\text{itr}$ とすると $f(X) = \lfloor (\sum_{i=1}^{\text{itr}-1} C_i + X(n-\text{itr})) / X \rfloor$ となる．よって $f(X)\ (1\leq X\leq N)$ を $O(NlogN)$ で求めることができた．
公式解説と比べて二分探索をしている分logがついているが，数式変形が楽(主観)な気がした．

あとは， $K\ (1 \leq K \leq N)$ について $K \leq f(X)$ であるような最大の $X$ を二分探索を用いて求めればよい．

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync\_with\_stdio(0); }}fastiofastio;
#ifdef DEBUG\_ 
#include "../program\_contest\_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i], a[i]--;

    vector<ll> cnt(n);
    REP(i, n) cnt[a[i]]++;
    sort(ALL(cnt));
    vector<ll> sum(cnt);
    FOR(i, 1, n) sum[i] += sum[i-1];

    vector<ll> f(n+1);
    FOR(x, 1, n+1) {
        ll itr = upper\_bound(ALL(cnt), x) - cnt.begin();
        f[x] = ((itr==0?0:sum[itr-1]) + x*(n-itr)) / x;
    }

    FOR(k, 1, n+1) {
        auto check = [&](ll mid) { return k <= f[mid]; };
        ll lb = 0, ub = n+1;
        while(ub-lb>1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) lb = mid;
            else ub = mid;  
        }
        cout << lb << endl;
    }

    return 0;
}