ABC154-D Dice in Line

精進録

初めて茶Diffを解いた記念。

提出コード:

https://atcoder.jp/contests/abc154/submissions/10555998

 

考えたこと

  • 問題文、制約を読む(3分)

期待値か、とりあえず定義に従って期待値を返す関数を作ろう！→関数を実装(2分)

NとKがまあまあ大きいから、愚直に二重ループじゃ駄目そうだなあ……どうしよう(3分うなる)

  • 自分の関数を眺める(2分)

期待値は(1+p)/2→期待値には加法性があるから、結局部分数列の和の最大化問題だ！

どうやったらいいだろう……そういえば累積和を使えばできそうだなあ……？

  • 累積和を書く(10分弱)

まあこんな感じでいいかな？数列の和の最大を求めてからkを足して2で割ることに注意して……Submit！

  • バグる(10分)

サンプル通ったからまあまあ合ってると思うんだけど……→出力部分をよく読むと「誤差10^-6までならOK」って書いてある→ってことは小数点以下の桁数が足りてないのかな→直してSubmit！→AC！