JOI2018/2019 予選ページ：E - イルミネーション (Illumination)

問題

https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t5-review.html

数列 {a_N} と M 個の区間 (L_i, R_i) が与えられる。数列 {a_N} からいくつかの要素 a_i を選び、その総和を求める。ただし M 個の区間に含まれる要素は 1 つしか選ぶことができない。

この時、総和の最大値を求めよ。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le a_i \le 10^9
  • 1 \le L_i \le R_i \le N

考え方

区間に含まれる要素は 1 つしか選ぶことができない点が重要である。つまり区間に含まれる a_i を選んだとき、i を被覆する区間のうち、R_i の最大値を rmax_i とすると次に選ぶことができるのは a_{rmax_i+1} である。

区間の最大値は数列の左から決めていくことができるのでDPで求めることができる。予め i を選んだときに制約区間に被覆される最大の R_i を求めておく。

dp \lbrack i+1 \rbrack := i 番目までの総和の最大値

とする。DP遷移は、a_i を選ぶ場合と選ばない場合のそれぞれで定まり、

a_i を選ばない場合は

dp \lbrack i+1 \rbrack = max(dp \lbrack i+1 \rbrack, dp \lbrack i \rbrack)

である。a_i を選ぶ場合は

dp \lbrack rmax_i+1 \rbrack = max(dp \lbrack rmax_i+1 \rbrack, dp \lbrack i \rbrack + a_i)

である。解は dp \lbrack N \rbrack となる。

Submission #3836041 - JOI2018/2019 予選ページ

どこに着目して考察するべきだったか

制約によって、a_i を選ぶ場合は次に選ぶことができるのは rmax_i+1 の要素であることがわかると、配るDPに気づけるかもしれない。

何がバグっていたか

得た知見

  • 区間を左から順に処理していく (適切に区間の始点や終点でソートしておく)
  • マスを左から順に処理していく

類題