JOI2018/2019 予選ページ D:日本沈没 (Japan Sinks)
問題
https://beta.atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d
制約
考え方
海面を一番上から順番に下げていく方針で考える(日本出現)。
海面が下がったときに、陸地が新たに出現する場合を考える。ある区画 について の場合に新たに出現することになる。ただし上記は実際には少し間違っていて、 と は同じ高さである可能性がある。その場合は つの陸地が出現したとみなさないといけないので、左方向 については同じ高さも許容することとする。
よって新たに陸地が出現する場合は以下の条件になる。
逆に陸地が減る場合は、今まで分かれていた つの陸地が つの陸地になるということである。これは の場合である。
なお、 の高い順にソートして上から順番に考えたいが、 だとメモリにもてないので座標圧縮する。この場合は上下関係のみが重要であるから、座圧して問題ない。
https://beta.atcoder.jp/contests/joi2019yo/submissions/3790997
どこに着目して考察するべきだったか
陸地が新たに出現する場合の条件、陸地が減る場合の条件の考察が重要。