ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

mod N

問題
提出コード

解法

引きわけがネックなので、どうにか別処理できないか、を考えてみます。すると、

  • e[i] = i回勝負がつくまでにかかるゲームの回数の期待値

とすると、
e[i] = e[i] \times \frac{C}{100} + e[i-1] \times \frac{A+B}{100} + 1
から、
e[i] = \frac{e[i-1] \times (A+B) + 100}{A+B}
と計算することができます。
この計算により、i回でゲーム全体が終了する場合について、e[i]と、高橋君、青木君の勝つ回数およびその順番(順列)のみ考慮すればよくなります。
仮に高橋君がN回勝つとすると、青木君はi-N回勝つことになります。この確率は\frac{A^{N}B^{i-N}}{(A+B)^{i}}となります。逆の場合もほぼ同様です。
i回目の勝負の決着が高橋君の勝ちになりますが、それ以外の1~i-1回目は、順番を自由に決めることができます。
この順番は、_{i-1}C_{N-1}通りです。
ということで、i回の勝負の決着でゲーム全体が終了する場合のゲーム回数の期待値は、
e[i] \times _{i-1}C_{N-1} \times (\frac{A^{N}B^{i-N}}{(A+B)^{i}}+\frac{A^{i-N}B^{N}}{(A+B)^{i}})
となります。A,B,A+Bの累乗は前計算をしておくことでO(1)で参照できます。あとは、N \leqq i \leqq 2N-1 \leqqのiについて上の計算をしていき、総和を求めれば答えになります。

感想

引き分けの部分をうまく別処理する方法を思いつくのに時間がかかりました…
最初は、dp[i][j] = 高橋君がi回、青木君がj回勝つときのゲームの回数の期待値、とすると、i =N or j = Nの場合を除き、
dp[i][j] = dp[i][j]\times \frac{C}{100} + dp[i-1][j]\times \frac{A}{100} + dp[i][j-1] \times \frac{B}{100} + 1
という部分から考えていきました。この計算だと時間が間に合わないので、Cに関する部分を別処理したくなるのですが、うまくA,Bの順列を組み合わせないといけないため、考察に時間がかかりました。