天下一プログラマーコンテスト2016予選B C. 天下一プログラマーコンテスト1999

問題

参加者はN人の総当たり戦の記録をアンドウくんとハシモトくんの2人が行う。
記録はN*Nの表に記録する。(1選あたり2つの記録をする)
アンドウくんは間違えずに記録するが、ハシモトくんは確率Pで正しい記録、確率(1-P)で間違った記録をしてしまう。
各記録は独立事象とし、勝ち数が多い順(同勝ち数の場合は表の並び順)から順位をつける。
アンドウくんの記録が与えられるので、アンドウくんとハシモトくんのそれぞれの記録からの順位付けが一致する確率を求めよ。

制約

• 2 <= N <= 30
• Pは「p/q」形式で与えられ、0 <= p <= q, 1 <= q <= 10

解法

順位を決める要素は勝ち数なので、まず「勝ち数」を考える。
ハシモトくんの記録での各参加者の勝ち数は確率的に変化するが、「ハシモトくんの記録でt勝になる確率」は「アンドウくんの方での記録(s勝)」「確率P」から考えることができる。

dp[s][t] := アンドウくんの記録でs勝だった人が、ハシモトくんの記録でt勝になる確率

これはハシモトくんが正しくつけた記録の数uで場合分けが必要で、

• 試合数(N-1)中、「s勝」「(N-1-s)敗」
• s勝のうち、u個正しくつけた
  • u個が勝ち->勝ち、(s-u)個が勝ち->負け、(t-u)個が負け->勝ち、(N-1-(t-u))個が負け->負け
• m個の記録のうち、n個正しくつけた場合の確率は、「mCn * P^n * (1-P)^(m-n)」で求められるのでこれをdp2[m][n]とする

と、

dp[s][t] =  Σ_{u=0}^{s} dp2[s][u] * dp2[N-1-s][(N-1-s)-(t-u)]

となる。

次に、ハシモトくん記録での順位変動を考える。
ある参加者について、記録間違いで勝ち数が変動しても順位が変動しない場合、というのはイメージできる。
順位が変動しない勝ち数の範囲は、他の参加者の勝ち数状況に依存しており、すべての各参加者の勝ち数を全探索することは計算量的に難しい。
そこで、動的計画法的に端から決めていく方法を考える。

順位が低い方から考える。
今、p位の人Xを考えると、p位の人Xの勝ち数がm、(p+1)位の人Yの勝ち数がnとすると、

• 表でXよりYが下の場合、m>=n
• それ以外の場合、m>n

となっていれば順位が変動しない。
この条件を踏まえて、「p位の人が勝ち数q以下で、順位変動しない確率f(p,q)」を考える。最終的な答えはf(1,N-1)。

p==Nの場合、最下位の人を考える場合で、「k=0勝～q勝でのdp[最下位の人の勝ち数][k]の和」になる。
p

• 同じ勝ち点が許されるならr=k
• 同じ勝ち点が許されないならr=k-1

として求める。

反省

実際の考えの流れは「勝ち数が重要」→「一致する確率は勝ち数に基づくdpで求められそう」→「dpの計算で必要となるハシモトくん記録で勝ち数tとなる確率、を求める方法を考える」という流れかも。

「確率の式を正しく出す」「勝ち数のdpの適用を思いつける」「場合分けをミスらない」「誤差死がでないか判断できる」など必要。