SRM418 Div2 500

問題

あなたは1からnまでのm個の違った数字を選ぶ。相手も同様に選ぶとき、もし、少なくともk個の数字が同じであればあなたの勝ちとなるとき、このゲームに勝つ確率を求める。

考え方

自分の選んだm個からi個が重なるときは選んでない(m-n)個から(m-i)個選ぶことになるので、m_C_i * (n-m)_C_(m-i)が選ぶ組み合わせの数になる。iはk以上m以下のものでありえるもの。
あとはすべての組み合わせがn_C_mなので、上記を足し合わせたものをn_C_mで割ったものが答え。

反省

数が少ないので全探索しても間に合う。