- 考えたこと
- 前の値xが与えられた時、サイコロごとに「そのサイコロを振って成功する」の確率が求まる
- 目が小さい方が成功確率は高いが、次のサイコロの成功率が下がる
- サイコロは3×10^4、目は1.8×10^5、全て異なる
- xは目の値しかとりえないので、ソートして大きい方から計算する
- 最大のxのとき、期待値は0
- DPで計算できる
- 素朴にDPすると、全部のサイコロのうち期待値を最大にするものを探すところでコスト掛かって10^9を超える
- すべての目が異なることから、xを1歩小さくした時に「目とxの大小関係」が変化するサイコロは1個だけ
- 何が変化するかに注目
- しかも単調増加
- 期待値最大のサイコロと更新されたサイコロを比較して、期待値の大きい方を取る、定数オーダーでできる
- これで間に合う
- 前の値xが与えられた時、サイコロごとに「そのサイコロを振って成功する」の確率が求まる
- 公式解説
- 目は大小関係しか使わないのでソートして連番に振り直しても良い=座標圧縮