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

Theme Color

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_b

方針

\( 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)!}\]

となります。

コード

感想

対数の計算で積は和に分解できることがポイントだと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする