abc143_f Distinct Numbers

原因

列を取り出す個数の方を固定して最大の長さを考える

↑この考察がどうひねっても出てこなかった

問題

https://atcoder.jp/contests/abc143/tasks/abc143_f

$N (\le 3 \times 10^{5})$ 個の整数 $A_i \in [1,N]$ から、相異なるちょうど $K$ 個の整数からなる組を最大いくつ取り出せるか。

$K = 1, 2, \ldots, N$ のそれぞれについて求めよ。

自力考察

長さ $K$ の狭義単調増加列を何個取り出せるか、と読み替える。

$C_j$ を $A_i = j$ なる $i$ の個数、$D_k$ を $C_j \textcolor{magenta}{\le} k$ なる $j$ の個数とするまでは良かったが、$\sum D_k / K$ がダメだったため頭を抱える。（ちょっと $D$ の定義が違うけど誤差）

反例： $A=\{1,1,2,3,4,5,5\}$ （→ $D = \{5,2\}$）で $K=3$ のとき。

解説AC

$X(1 \le X \le N)$ 個の列を取り出すときの最大の長さを表す関数 $f(X)$ を考えます。

天才

$X$ 個の列を取り出すとき、各整数 $j \in [1,N]$ は高々 $X$ 回しか使えないのでそれを超える分を無視しても一緒。あとは各列に整数を満遍なく割り振ることで、各列の長さの（最小値の）最大を実現することが可能である。

以上を式で表すと

$$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor $$

となる。すべての $X$ について $f(X)$ を求めたあとは各 $K$ について $K \le f(X)$ を満たすような最大の $X$ を出力すればよい。

考察

解説下段の $f(X)$ の式変形が面倒（というか絶対思いつけなさそう）なので元の式 $$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor $$ からなんとか考察したい。

$C_j$ は$A_i = j$ なる $i$ の 個数 なので、$C_j$ の昇順にソートしても差し支えない。ここで、二分探索によって $C_j \le X$ となる最大の添字 $j = J$ を求めることで、 $$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor = (N-J) + \left\lfloor \frac{\sum_{j=1}^J C_j}{X} \right\rfloor $$

と求めることができる。これは予め $C$ の累積和を求めておけば時間 $O(\log N)$ で求められるので、全体で $O(N \log N)$ で解ける。

あとは $X=0$ でバグらないようにして完成。

提出コード

初AC（添字お祈りゲーをした）: https://atcoder.jp/contests/abc143/submissions/9960709

リファイン版: https://atcoder.jp/contests/abc143/submissions/9961265

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(int)(n);i++)

int n,a;
vector<int> c, rui;

int f(int x){
    auto it = lower_bound(c.begin(), c.end(), x);
    int i = (int)(it - c.begin());
    return (n-i) + rui[i] / x;
}

signed main(){
    cin >> n;
    c.resize(n);
    REP(i,n){
        cin >> a;
        c[a-1]++;
    }
    sort(c.begin(), c.end());
    rui.resize(n+1);
    REP(i,n) rui[i+1] = rui[i] + c[i];

    int ans = n;
    REP(i,n){
        while(ans && f(ans) < i+1) ans--;
        cout << ans << "\n";
    }
}

感想

解説通りにACとならないときに、こういう記事に自分の考察まとめるのこそ競プロブログって感じがする

変数の方を固定してなんとかする発想は言われてみれば頻出な気がしてきたので今後頑張ります

_ が2個あると装飾が優先されるからエスケープする