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

確率・期待値DP

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

問題

数学

• yukicoder No.813 ユキちゃんの冒険

恐らくアドホック

• yukicoder No.475 最終日 - Writerの怠慢 解説

ある部分を全探索して求める

• yukicoder No.574 正多面体サイコロ 解説

確率DP

• CF New Year and Arbitrary Arrangement
• EDPC Coins 解説
• SRM747 Div1 Med TieForMax 解説

再帰関数系(木DP？)

• CF362 Puzzle 解説1 解説2 解説3
• CF62 Half-decay tree 解説

期待値DP

• yukicoder No.76 回数の期待値で練習 解説1 解説2
• yukicoder No.108 トリプルカードコンプ 解説
• ARC016 C - ソーシャルゲーム 解説
• Typical DP Contest J - ボール
• CF157 Little Elephant and Broken Sorting
• SRM729 Div2 Hard RareItems 解説
• SRM731 Div1 Med RndSubTree
• EDPC Sushi 解説

期待値の線形性

• AC Ordinary Beauty
• AC デフレゲーム
• AGC028 Removing Blocks
• AC Inversion Sum

クエリ系？

• CF New Year Santa Network

未解決

• http://agc007.contest.atcoder.jp/tasks/agc007_c
• AOJ カジノ 解説