phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

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

問題

高橋くんと青木くんが、どちらかが合計N回勝つまでゲームを繰り返す。
1回のゲームでは、高橋くんが勝つ確率はA%、青木くんが勝つ確率はB%、引き分けになる確率はC%である。

ゲームが行われる回数の期待値を出力せよ。
ただし、期待値は小数ではなく、互いに素なP,Qを用いて期待値がP/Qと表せるとき、R*Q=P (mod 10^9+7)となる整数Rで答えよ。

制約

  • 1 <= N <= 10^5
  • 0 <= A,B,C <= 100
  • 1 <= A+B
  • A+B+C = 100
  • 入力はすべて整数

解法

(解説の方法)
Nの制約からO(N^2)な解法は許されない。

まず、引き分けについて考える。
引き分けは、そこまでのゲーム内容とは無関係にC%の確率で起こる。
そのため、勝ち負けが決まるようなゲームの内容に依存せずに考えられる。

依存するのは、勝ち負けが決まるようなゲームの回数で、これがM回だった場合、引き分けの回数の期待値が求められる。(ゲームを遅滞させていると考えられる。どのぐらい遅滞させるか?)
これは、「勝ち負けが決まるゲームが行われる確率が(100-C)/100、引き分けになるゲームが行われる確率がC/100のとき、勝ち負けが決まるゲームがM回行われる場合の、ゲームの行われる回数の期待値は?」という問題と考えられる。
これは、E_{勝ち負けが決まるようなゲームの回数}を残り何回ゲームを行うか?の期待値として、1回分だと、

E_0 -> E_1
↓↑

のような遷移であり、
E_0 = 1 + (100-C)/100 * E_1 + C/100 * E_0
E_1 = 0
と書けるので、
E_0 = 100/(100-C)
となる。
M回分で考えると、E_M = M * 100/(100-C)となる。
よって、勝ち負けが決まるようなゲームの回数がM回の場合、引き分けも含めて行われるゲームの回数の期待値は「M * 100/(100-C)」回である。

あとは、勝ち負けが決まるようなゲームの回数がM回であるような確率を求められれば、上記の回数に掛けることで全体の期待値を求められる。


勝ち負けが決まるゲームで考えた場合、N回以上2N回未満の回数で勝負が決する。
これをM回と置くと、M回のうち、高橋くんが勝つケースでは、M回目は高橋くんである必要があり、M-1回目までで高橋くんがN-1回勝っている必要がある。
これは、組み合わせを用いて、{M-1}_C_{N-1} * (A/(A+B))^N * (B/(A+B))^{M-N}の確率で起きる。
青木くんについても同様で、{M-1}_C_{N-1} * (B/(A+B))^N * (A/(A+B))^{M-N}の確率で起きる。
よって、上記の2つを足し合わせたものが、M回で勝負が決する確率になる。

あとは、MをN~2N-1でループを回し、Mの時の確率と上記の期待値をかけたものを足し合わせていけばよい。
(mod_conv, mod_inverse, mod_powあたりが必要)

反省

コンテスト中はO(N^2)な解法から計算量を落とそうと考えて、ごちゃごちゃいじっていたら終わってしまった。。。

O(N^2)の解法は、
E_{x,y} := 高橋くんの勝ち数がx、青木くんの勝ち数がyのとき、ゲームの残り回数の期待値
と考えると、

E_{x+1,y} <- E_{x,y} -> E_{x,y+1}
               ↓↑

のような遷移になっていて、再帰的に、
E_{x,y} = 100/(100-C) + A/(A+B) * E_{x+1,y} + B/(A+B) * E_{x,y+1}
E_{N,*} = E_{*,N} = 0
E_{0,0} = ?
と書ける。
(引き分けの部分も依存してしまっていて分離できなかった)