noteレッドコーダーへの道のりは遠い。高橋くんと青木くんが、どちらかが合計N回勝つまでゲームを繰り返す。1回のゲームでは、高橋くんが勝つ確率はA%、青木くんが勝つ確率はB%、引き分けになる確率はC%である。ゲームが行われる回数の期待値を出力せよ。10^9+7)となる整数Rで答えよ。解法(解説の方法)Nの制約からO(N^2)な解法は許されない。引き分けについて考える。引き分けは、そこまでのゲーム内容とは無関係にC%の確率で起こる。そのため、勝ち負けが決まるようなゲームの内容に依存せずに考えられる。依存するのは、勝ち負けが決まるようなゲームの回数で、これがM回だった場合、引き分けの回数の期待値が求められる。(ゲームを遅滞させていると考えられる。どのぐらい遅滞させるか?)これは、「勝ち負けが決まるゲームが行われる確率が(100-C)/100、引き分けになるゲームが行われる確率がC/100のとき、勝ち負けが決まるゲームがM回行われる場合の、ゲームの行われる回数の期待値は?」という問題と考えられる。100/(100-C)となる。100/(100-C)となる。100/(100-C)」回である。あとは、勝ち負けが決まるようなゲームの回数がM回であるような確率を求められれば、上記の回数に掛けることで全体の期待値を求められる。勝ち負けが決まるゲームで考えた場合、N回以上2N回未満の回数で勝負が決する。これをM回と置くと、M回のうち、高橋くんが勝つケースでは、M回目は高橋くんである必要があり、M-1回目までで高橋くんがN-1回勝っている必要がある。(B/(A+B))^{M-N}の確率で起きる。(A/(A+B))^{M-N}の確率で起きる。よって、上記の2つを足し合わせたものが、M回で勝負が決する確率になる。あとは、MをN~2N-1でループを回し、Mの時の確率と上記の期待値をかけたものを足し合わせていけばよい。mod_powあたりが必要)反省コンテスト中はO(N^2)な解法から計算量を落とそうと考えて、ごちゃごちゃいじっていたら終わってしまった。HxWのグリッドにコインがいくつか置かれている。m本の腕とm+1個の関節からなるロボットアームを考える。»プロフィールid:phyllo_algoレッドコーダーへの道のりは遠い。)はてなブログをはじめよう!phyllo_algoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。