[AtCoder] CODE FESTIVAL 2018 Final (Parallel) B – Theme Color

問題

方針

\( p \) を計算する

ある人があるの色に投票する確率は色によって変わらないので、この確率を \( a \) とすると、
\[ a = \dfrac{1}{M}\]
となります。色 \( i \) に \( r_i \) 票集まる確率が \( p \) なので、どのくらい票が偏っているかを表すのが \( p \) になります。つまり、全ての色の票数が \( \dfrac{N}{M} \) 票であれば、偏っていないことになります。

場合の数として考えると、\( N \) 個の番号が割り振られたボールを、\( N \) 回に分けて取り出すことを考えます。\( i \) 回目に取り出されるボールの個数が \( r_i \) に当たります。

場合の数を元に確率を考えると、\(S_i = r_1 + r_2 + \cdots + r_i \) 、\( S_0 = 0\)、\(b_i = N – S_{i – 1} \) とすると、

\[p = {}_{b_1} \mathrm{ C }_{r_1} a^{r_1} {}_{b_2} \mathrm{ C }_{r_2} a^{r_2} \cdots {}_{b_N} \mathrm{ C }_{r_N} a^{r_N}\]
となります。

\( x \) を求める

\( p \leq 10^{-x} \) を求めればよいので、\( -\log_{ 10 } p \geq x \) とします。
\( \log_{ 10 } {a^{r}} = -r\log_{ 10 } M\) であり、
\[ \log_{ 10} {N!} = \log_{ 10 } {1} + \log_{ 10 } {2} + \cdots + \log_{ 10 } {N}\]
であることを利用すると、\( \log_{ 10 } {p}\) を計算することができます。よって、\( x = \lceil -\log_{ 10 } {p}\rceil\) となります。
また、二項係数を階乗で表現すると、
\[{}_{n} \mathrm{ C }_{k} = \dfrac{N!}{k!(N – k)!}\]
となります。

コード

提出したコード

 

AtCoder,数学

Posted by ヤマカサ