JOI難易度６ 日本沈没

問題原文

atcoder.jp

問題要旨

日本列島は横長い島であり、地点 の高さは である。
また海面の高さは０であり、海面より高い部分を陸地、陸地が１つ以上連続している区間を島と呼ぶ。
海面が徐々に高くなっていくと、島の数が増減し、最終的には０になる（日本沈没）してしまうが、それまでに島の数は最大でいくつになりうるか？

• 
• 

解法

ある時間になったら辺が消えて〜みたいなイメージ。そしてそういう問題は、辺を切っていくよりも辺を追加していくと考えたほうが扱いやすい。
よって初期状態は完全に沈没しきった状態とし、そこから時間を巻き戻すように地点を追加していく。 地点の追加においては、その両隣が陸なら島の数は-1, 片方が陸なら変化なし, 両隣が海なら+1となる。
2111112 のようなケースが扱いづらそうだが、よく考えると伝播するので大丈夫となる。

実装

最初から海（ =0）になっていることがあるのでそこだけ気をつける。
両隣を見るのは番兵をおくと楽。

N = int(input())
A = list(map(int, input().split()))
A = sorted([[a, i] for i, a in enumerate(A)])

ans = 0
X = [0] + [0] * N + [0]  # 番兵つき

ans = 0
island_cnt = 0
while A:
    m = -1
    while A and (m <= A[-1][0]):
        a, i = A.pop()
        m = a

        if m == 0:
            break

        X[i] = 1
        island_cnt += 1

        if X[i - 1]:
            island_cnt -= 1

        if X[i + 1]:
            island_cnt -= 1

    ans = max(ans, island_cnt)

print(ans)

感想

削るのが難しい → 無に追加していく の転換は典型ですね。
UF問題でよくでるイメージです。