はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける確率・期待値問題

確率・期待値DP

  • 「dp[i] := ~となる確率・期待値」でDPする
  • とても良い資料
  • 期待値DPの優良資料
  • 使える知識
    • 期待値の線形性
    • 「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」(出典)
    • Nターンあったら、各ターンは別々に期待値が計算できたりする(これって線形性?)問題
    • 【テク1】2つのものを1つにまとめる計算をどんどんしていくと、最終的に1つになって、それが答え