ABC166 C - Peaks から恩情を受ける

15922 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク




なんというか、グラフでやりたかった。
以下の記事も参考にしつつ、書いてみた。

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 の入力には重複が見られたので
コメントにある ココから、ココまでの領域で
重複を取り除く記述を追加している。

。。無くても、あっても一応通る。