Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-04-28

CodeChef April Cook-Off : The Grand Cook Off の証明 (というか計算方法)

| 08:17

終了後も証明ができずにうんうん唸っていたのでそのまとめ。

確率とか場合の数とか苦手...

間違ってたら指摘をお願いします。



1.定式化

参加者を、ブロックAとブロックBに分けて、ブロックAの優勝者とブロックBの優勝者の得点の差を求める、と置き換えて良い。


2.全体の場合の数

n人のブロックで優勝者を決めるには、n-1試合が行われるので、

(nC2)*2 * ((n-1)C2)*2 * ... * (2C2)*2 = n! * (n-1)!

通りの場合がある。


同じように、n人のブロックで決勝進出の2人を決めるには、n! * (n-1)! / 2 通りの場合がある。(n>1)

ただし、ブロックAとブロックBに分けて考える場合、AとBが丸々逆になった場合が重なってしまうので、方便として全体を2倍してn! * (n-1)!通りとする。


3.ブロックAに参加者がk人いて、その得点の合計がa点になる場合の数

n人中k人選んで得点の合計がa点になる組み合わせの数(試合順は無視)をdp[k][a]とする。

これはDPで求められる。

この時、ブロックBには参加者がn-k人いることに注意すると、求める事象の数は、

dp[k][a] * (k! * (k-1)!) * ((n-k)! * (n-k-1)!) * (n-2)C(k-1)

= dp[k][a] * k! * (n-k)! * (n-2)!

(n-2)C(k-1)が係るのは、ブロックAとブロックBの試合順が混ざることがあるから。


ちなみに、sum(dp[k][a] for all(a)) = nCk であることに注意すると、

sum(dp[k][a] * k! * (n-k)! * (n-2)! for all(k, a))

= sum(n! * (n-2)! for all(k))

= n! * (n-1)!

となることが確かめられる。


4.ブロックAに参加者がk人いて、その得点の合計がa点になる確率

個々の事象の起こる確率は、(その事象の起こる場合の数)/(全体の場合の数)で求められる。

なので、

p(k, a)

= (dp[k][a] * k! * (n-k)! * (n-2)!) / (n! * (n-1)!)

= dp[k][a] / nCk / (n-1)

となる。


5.結論

数学難しい。