PAST1O

https://gyazo.com/a96588a2faae92214acd0e7b6e653209

考えたこと

前の値xが与えられた時、サイコロごとに「そのサイコロを振って成功する」の確率が求まる

目が小さい方が成功確率は高いが、次のサイコロの成功率が下がる

サイコロは3×10^4、目は1.8×10^5、全て異なる

xは目の値しかとりえないので、ソートして大きい方から計算する

最大のxのとき、期待値は0

DPで計算できる

素朴にDPすると、全部のサイコロのうち期待値を最大にするものを探すところでコスト掛かって10^9を超える

すべての目が異なることから、xを1歩小さくした時に「目とxの大小関係」が変化するサイコロは1個だけ

しかも単調増加

期待値最大のサイコロと更新されたサイコロを比較して、期待値の大きい方を取る、定数オーダーでできる

これで間に合う

公式解説