きろく

特筆すべき記録のまとめ

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

問題

atcoder.jp

解法

引き分けがない(勝ち負けが必ずつく)として考えると,ゲームが行われる回数 M は N <= M <= 2 * N - 1 の値を取りうる.それぞれの M に対する決着がつくまでの確率は,a = A / 100, b = B / 100 とおくと,

C(M - 1, N - 1) * (a^N * b^(M - N) + a^(M - N) * b^N)

となる.二人とも N - 1 勝目まではどのタイミングで勝ってもかまわないため C(M - 1, N - 1) をかけている.

次に M に対して引き分けがどれだけ起こるかの期待値を求める.これは直感的に M * (100 / 100 - C) となる(証明略).

これで各 M について確率と全部のゲーム数の期待値が求まったので,あとは考えられる M それぞれについてこの 2 つをかけて全て足し合わせたものが答えとなる.O(N).

解答

atcoder.jp

f:id:babcs2035:20190605174956p:plain