[yukicoder] No. 1220 yukipoker

問題

方針

全ての手札の組み合わせは \( {}_{NM} \mathrm{ C }_{K} \) 通りありますが、確率を比較するうえでは必要ありません。フラッシュの総数は、同一のソートから \( {}_{N} \mathrm{ C }_{K} \) 通りあり、\( M \) 種類のソートがあるので、\( M{}_{N} \mathrm{ C }_{K} \) 通りあります。ストレートについては、連番の組み合わせが \( N – K + 1 \) 通りあり、ある数字に対して \( M \) 種類から選べるので、\( (N – K + 1)M^K\) 通りあります。

ここで、

\[ \log {}_{N} \mathrm{ C }_{K} = \log N! – \log K! – \log(N-K)!\]

となります。また、

\[ \log N! = \log 1 + \log 2 + \cdots + \log N\]

となるので、累積和を用いて高速に計算することができます。

したがって、フラッシュの総数の対数を取ったものを \( F \)、ストレートのものを \( S \) とすると、

\begin{eqnarray}
F &=& \log M + \log N! – \log K! – \log(N-K)!\\
S &=& \log (N – K + 1) + K \log M
\end{eqnarray}

を比較すれば良いです。

コード

 

感想

階乗の対数を取って計算する問題を以前解いたことがありました。