Atcoder ABC 154 D - Dice in Lineをpythonで解く

コード本文

ABC154に参戦した。

この頃、競プロを少しかじっているので結構いい感じに解けるんじゃないかと思ったが、Cまでしか解けなくて落胆。

後日、解けなかったD問題を復習した。

以下通ったD問題のコード本文

abc154 d問題

コード解説

この問題で使うテクニックはしゃくとり法(または累積和)と期待値の基本的な知識

コードの流れは以下の通り

1. 配列に収めたサイコロのそれぞれの期待値を事前に算出しておく。このときp種類の目が出るサイコロの目の期待値は(1+p) / 2であることに注意

2. しゃくとり法、または累積和を使って期待値の配列から長さがkの最大部分配列を算出する。

私はステップ1の期待値算出のところで期待値を(1+2+...+p) / pと計算してしまいTLEで爆死。

感想

ちょっといいスコア出るんじゃないかなと期待しつつ参戦したのにこの結果はかなり落ち込む。

とりあえず、数学、高校生からやり直してきます。