ABC166 C - Peaks에서 은혜를 받다

어쩐지, 그래프로 하고 싶었다.
이하의 기사도 참고로 하면서 써 보았다.


Peaks_r0.py

n,m = map(int,input().split())
H = list(map(int,input().split()))

memo = [[] for _ in range(n)]     #各展望台からつながる道をストック
lis = [False]*n                   #行ったことあるか、無いかを記録
for _ in range(m):
    a,b = map(int,input().split())
    memo[a-1].append(b-1)
    memo[b-1].append(a-1)
#print(memo)

cnt = 0
for i in range(n):
    if memo[i]:
        #print(memo[i])
        for j in range(len(memo[i])):# start / end 地点、両方を記録
            lis[i] = True            # start
            lis[memo[i][j]] = True   # end

        for j in range(len(memo[i])):#for else を使い、start 地点が一番高い事を確認
            if H[i] <= H[memo[i][j]]:
                break
        else:
            #print(memo[i])
            cnt += 1                 #一番高かったらカウント

#print(lis)
print(cnt+lis.count(False))          #一度も行ったことない所は False なので,False をカウントし、
                                     #cnt との合算が答え

우선, 하고 싶은 일을 할 수 있었고, 다니기 때문에
기뻤지만, 정말로 이것으로 좋은 것인지, 의문이 남았다.
왜냐하면 계산량이 많기 때문이다. 왜 다녔어? ?

Peaks.py

n,m = map(int,input().split())
H = list(map(int,input().split()))

memo = [[] for _ in range(n)]     
lis = [False]*n                   
for _ in range(m):                   #O(10^5)
    a,b = map(int,input().split())
    memo[a-1].append(b-1)
    memo[b-1].append(a-1)
#print(memo)

cnt = 0
#ここから→#####
for i in range(n):                   #O(10^5)
    if memo[i]:
        #print(memo[i])
        for j in range(len(memo[i])):#O(10^5)
            lis[i] = True            
            lis[memo[i][j]] = True   

        for j in range(len(memo[i])):#O(10^5)
            if H[i] <= H[memo[i][j]]:
                break
        else:
            #print(memo[i])
            cnt += 1
#ここまで←###### O(10^5 * 2*10^5)


#print(lis)
print(cnt+lis.count(False))        

적게 견적해도 O(2*10^10 + 10^5)처럼 보인다.
은정을 받은 것 같았다.

견식을 넓히고 다시 도전하자.

재챌린지했지만 다양한 최적화를 할 수 있었다.

abc166c.py

N,M = map(int,input().split())
H = list(map(int,input().split()))

lis = [[] for _ in range(N)]
dic = {}
for _ in range(M):
    a,b = map(int,input().split())
    x = str(a)+str(b)## => ココから
    if x not in dic:
        dic[x] = 0
    dic[x] += 1
    if dic[x] == 1:##<= ココまで
        lis[a-1].append(H[b-1])
        lis[b-1].append(H[a-1])

#print(lis)
cnt = 0
for i in range(N):
    if len(lis[i])==0 or H[i] > max(lis[i]):
        #print(H[i],lis[i])
        cnt += 1
print(cnt)

A, B 입력에 중복이 있었기 때문에
코멘트에있는 코코에서 코코까지의 영역에서
중복을 제거하는 설명을 추가하고 있다.

. . 없어도, 있어도 일단 통과한다.