読者です 読者をやめる 読者になる 読者になる

だらだら〜個人事業〜

HatenaDiaryから引っ越してきました。Githubもnyakagawanです。

yukicoder No.335 門松ゲーム

No.335 門松宝くじ - yukicoder

普通に総当りで特攻してでかい数列のテストケースでTLE

解説を見るとセグメント木というデータ構造を使うとあるのでそれを調べる。

yousack.hateblo.jp

こちらとてもわかり易い解説。

解説を読んで「ある範囲の最大値と最小値を求める」というのに引っかかる…。
問題文を見直すと「D君は当選番号発表後に最も高い当選金額を得る選択をする。」とある。なるほど…、ベストケースだけ期待値に含まれれば良いのか…。というか、当選金額が低くなるパターンは回答として存在しないのか。

つづく