ABC017-C ハイスコア

 概要

https://atcoder.jp/contests/abc017/tasks/abc017_3

N個の区間とそれに対応する得点が与えられる。

それぞれ区間は1から始まる長さMの区間に含まれる。

区間を重ね合わせたときに1からMの区間と一致しないよう0個以上の区間を選ぶ。選び方について得点を合計し、その最大値を求めよ。

 解法

方針

区間[1,2)、区間[2,3)、...、区間[M, M+1)を含まないように区間を選んで得点を計算する。

求める解はその最大値となる。

優先度付きキューを使用し、将来使えなくなる区間と、現在使えない区間を管理する。

初期の除外区間を[0, 1)とすると、与えられた区間[L, R]はすべて将来使えなくなる区間に登録することになる。合計得点は与えられた区間の得点の合計値となる。

除外区間を1ずつ進めながら下記の処理を行うことで、すべての除外区間についての合計得点を求めることができる。

・将来使えなくなる区間のうち、左端が現在の区間にかぶるものは使えなくなるので、合計得点から得点を引き、現在使えない区間に登録する。

・現在使えない区間について右端が左のほうにあるものについて調べ、すでに左にあるものについては再び得点に加える。

https://atcoder.jp/contests/abc017/submissions/20210178