yukicoder No.335 門松ゲーム
普通に総当りで特攻してでかい数列のテストケースでTLE
解説を見るとセグメント木というデータ構造を使うとあるのでそれを調べる。
こちらとてもわかり易い解説。
解説を読んで「ある範囲の最大値と最小値を求める」というのに引っかかる…。
問題文を見直すと「D君は当選番号発表後に最も高い当選金額を得る選択をする。」とある。なるほど…、ベストケースだけ期待値に含まれれば良いのか…。というか、当選金額が低くなるパターンは回答として存在しないのか。
つづく
普通に総当りで特攻してでかい数列のテストケースでTLE
解説を見るとセグメント木というデータ構造を使うとあるのでそれを調べる。
こちらとてもわかり易い解説。
解説を読んで「ある範囲の最大値と最小値を求める」というのに引っかかる…。
問題文を見直すと「D君は当選番号発表後に最も高い当選金額を得る選択をする。」とある。なるほど…、ベストケースだけ期待値に含まれれば良いのか…。というか、当選金額が低くなるパターンは回答として存在しないのか。
つづく