Quiz
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_f
Submit
https://atcoder.jp/contests/iroha2019-day2/submissions/5216485
解法
- 公式解説と違う解き方で解いたので書いておく
- まず、くじ引きはいつ引いても平等というのがある
- たとえば100円2枚、50円2枚の箱を考える
- これは期待値75円で4回引ける箱である
- 1回引いた後も、期待値は変わらず75円である
- ということで、期待値が高い箱をそれぞれ貪欲に引いていけばいい
嘘解法？
- 結構自信を持ってこの解法を書いて提出しACしたのだが、上位の赤い人・黄色い人がDPで解いているのを見ると、嘘解法である可能性がある・・・
- この解法で解くと1msなのだが、1msでACしている人は7名
