h_nosonの日記

競プロ、CTFなど

期待値

yukicoder No.23 技の選択

問題 No.23 技の選択 - yukicoder 体力がの敵を 攻撃力の通常攻撃(必ず当たる) 攻撃力の必殺技(2/3の確率で当たる) の二つの攻撃を使って倒したい.最小の攻撃回数の期待値はいくつか. 解法 解説を見たら全部DPで解いていたが,通常攻撃の使う回数でル…

yukicoder No.174 カードゲーム(Hard)

問題 No.174 カードゲーム(Hard) - yukicoder A君とB君がカードでゲームを行う.1から1000までの数字が書かれたカードがあり,その中から枚ずつ配られる.試合は回あり,試合ごとにプレイヤーがカードを出していき,大きい数字を出したほうがその数字…

yukicoder No.210 探し物はどこですか?

問題 No.210 探し物はどこですか? - yukicoder 部屋が個あり,そのどこかにメガネがある. 番目の部屋にある確率がでその部屋を見た時に見つけられる確率がである. メガネを見つけるまでの部屋を見る回数の期待値を最小にする問題.解法 回目に番目の部屋…

yukicoder No.75 回数の期待値の問題

問題 No.75 回数の期待値の問題 - yukicoder 1つのサイコロを繰り返し振り,出た目の合計をにする. もしを上回ったら合計を0にリセットする. サイコロの振る回数の期待値はいくらか.解法1 絶対誤差か相対誤差がに収まればいいので モンテカルロでも正解を…