なんというか、グラフでやりたかった。
以下の記事も参考にしつつ、書いてみた。
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 の入力には重複が見られたので
コメントにある ココから、ココまでの領域で
重複を取り除く記述を追加している。
。。無くても、あっても一応通る。