PythonでJOI難易度6を埋める #15

D - 日本沈没 (Japan Sinks)

解説と同じ考え方をしたが，になった．海面を上げていくときに，それぞれの要素の両隣調べる方法が分からなかった． それぞれの高さのindexをdictに記録して，海面を上げたときの島の増減を計算する．参考にした提出．このコードの計算量はいくつ?

from sys import stdin
input = stdin.readline
from collections import defaultdict

n = int(input().strip())
a = list(map(int, input().strip().split()))

a_sorted = sorted(list(set(a)))
dic = defaultdict(list)

for i, j in enumerate(a):
    dic[j].append(i)

cnt = 0
flag = False #T→新しい陸地に入る
for i in a:
    if i > 0:
        if not flag:
            cnt += 1
            flag = True
    else:
        flag = False

if n == 1:
    if a[0] > 0:
        print(1)
    else:
        print(0)
else:
    ans = cnt
    for i in a_sorted:
        tmp = 0 #この変化での島の増減
        if i != 0:
            for j in dic[i]:
                if j == 0: #一番前のとき
                    tmp -= 1
                    if a[j + 1] > i: #±0
                        tmp += 1
                    elif a[j + 1] < i: #-1
                        tmp -= 1
                elif j == n - 1: #一番後ろのとき
                    tmp -= 1
                    if a[j - 1] > i: #±0
                        tmp += 1
                    elif a[j - 1] < i: #-1
                        tmp -= 1
                else:
                    if a[j - 1] > i:
                        tmp += 1
                    elif a[j - 1] < i:
                        tmp -= 1
                    if a[j + 1] > i:
                        tmp += 1
                    elif a[j + 1] < i:
                        tmp -= 1
        cnt += tmp // 2
        ans = max(cnt, ans)
    print(ans)

できたこと

• Aをsortして小さい順に取りだす
• 考える海面の高さは整数だけ
• 海面の高さが変化したときの島の個数の変動

学んだこと

• dictの中にlistを作れる