mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder 確率dp 確率 問題 問題概要 トーナメントで勝ち進んでいく確率。 解法 dpで解いた。 dp[i][j] := i回回目の試合にj番目のひとが勝つ確率 として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、 dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y] のようになる。これは、i回目まで、x番目の人と、y番目の人が勝ち上がっている確率に、x番目の人とy番目の人が戦った時に、x番目の人が勝つ確率をかけている。これをi+1番目にxさんが戦う可能性のある人全員に対して行い、それらの確率を合計することで、i+1番目の試合で、x番目の人が勝つ確率がわかる。 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F09%2F23%2F204548" title="yukicoder No.66 輝け☆全国たこやき杯 - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-09-23 20:45:48 rich https://mmxsrup.hatenablog.com/entry/2016/09/23/204548 1.0 100%