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

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

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

さ、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;
}