けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2018 Final B - Theme Color (300 点)

AtCoder AtCoder300点 unrated公式コン確率前処理競技数学色強め

さ、300 点！？

問題へのリンク

問題概要

$M$ 個の中からランダムに選ぶ試行を $N$ 回行う。それぞれのものが出た回数が $r_1, r_2, \dots, r_M$ 回になる確率を $p$ としたとき、 $p \ge 10^{-x}$ を満たすような最小の $x$ を求めよ。

制約

$1 \le N, M \le 10^{5}$

考えたこと

確率を求めること自体は難しくなくて、

$p = \frac{N!}{r_{1}! r_{2}! \dots r_{M}!} (\frac{1}{M})^{N}$

で求められる。が、この値はあまりにも小さくなりうるので対数をとる。具体的には log10 関数を用いる。そうすると

$x = {\rm ceil}(-\log{p})$

となる。あとは $\log(n!)$ を頑張って前処理で計算しておけば OK。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX = 101010;
const long double EPS = 1e-6;
vector<long double> p;

int main() {
    p.assign(MAX, 0);
    for (int i = 1; i < MAX; ++i) p[i] = p[i-1] + log10(i);
    int N, M;
    cin >> N >> M;
    long double prob = -p[N];
    for (int i = 0; i < M; ++i) {
        int r; cin >> r;
        prob += p[r];
    }
    prob += log10(M) * N;
    cout << ceil(prob) << endl;
}