JOI2018/2019 予選ページ D:日本沈没 (Japan Sinks)

問題

https://beta.atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d

制約

  • 1 \le N \le 10^5
  • 1 \le A_i \le 10^9

考え方

海面を一番上から順番に下げていく方針で考える(日本出現)。

海面が下がったときに、陸地が新たに出現する場合を考える。ある区画 A_i について A_{i-1} \lt A_i > A_{i+1} の場合に新たに出現することになる。ただし上記は実際には少し間違っていて、A_iA_{i-1} は同じ高さである可能性がある。その場合は 1 つの陸地が出現したとみなさないといけないので、左方向 A_{i-j} については同じ高さも許容することとする。

よって新たに陸地が出現する場合は以下の条件になる。

A_{i-1} \le A_i > A_{i+1}

逆に陸地が減る場合は、今まで分かれていた 2 つの陸地が 1 つの陸地になるということである。これは A_{i-1} > A_i \le A_{i+1} の場合である。

なお、A_i の高い順にソートして上から順番に考えたいが、1 \le A_i \le 10^9 だとメモリにもてないので座標圧縮する。この場合は上下関係のみが重要であるから、座圧して問題ない。

https://beta.atcoder.jp/contests/joi2019yo/submissions/3790997

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

陸地が新たに出現する場合の条件、陸地が減る場合の条件の考察が重要。

何がバグっていたか

得た知見

類題