M-SOLUTIONS プロコンオープン:C - Best-of-(2n-1)
問題
解法
引き分けがない(勝ち負けが必ずつく)として考えると,ゲームが行われる回数 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).
解答