srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

確率

yukicoder No.23 技の選択

問題 問題概要 省略。 解法 期待値dpの問題。 残りのHPを基準に考える(下のソース)。 aを選びとき、(残りHPがiのときの期待値) = (残りHPがi + aのときの期待値) + 1(回) bを選ぶとき、(残りHPがiのときの期待値) = (残りHPがi + bのときの期待値) + 1.5(回)…

yukicoder No.66 輝け☆全国たこやき杯

問題 問題概要 トーナメントで勝ち進んでいく確率。 解法 dpで解いた。 dp[i][j] := i回回目の試合にj番目のひとが勝つ確率 として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、 dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y] のように…

yukicoder No.58 イカサマなサイコロ

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

yukicoder No.57 ミリオンダイス

問題 問題概要 期待値問題。 解法 期待値の線形性を使うと簡単にできる問題。 ミス 数学ガール読みます。 コード #include <iostream> #include <cstdio> #include <set> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int </algorithm></set></cstdio></iostream>…

aoj 2301 - Sleeping Time

問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …