srupのメモ帳

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

期待値

yukicoder No.23 技の選択

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

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>…

yukicoder No.242 ビンゴゲーム

問題 問題概要 期待値の線形性を使う問題。 期待値の線形性を使う類題 No.144 エラトステネスのざる - yukicoder 解法 この問題のよくわからないところは、縦、横、斜めが独立でないので、どうやれば?て感じになる。ただ、どこか1列だけがビンゴする期待値…

yukicoder No.65 回数の期待値の練習

問題 問題概要 サイコロを降って、目の合計がK以上になるサイコロを振る回数の期待値を求める問題。 解法 漸化式を用いて動的計画法で解く。 ミス 漸化式をすこし間違えた。dp[i] := (これまでの目の合計が i のとき、合計が k になるまでに降ることになる回…