AtCoder Beginner Contest (ABC) 166　PythonでC問題解いてみた

前回解いたやつ

mery-kirokudayo.hateblo.jp

こんにちは。めりーです。

雨がひどい日が続いておりますが、いかがお過ごしでしょうか。
自分は雨が嫌いなのでお家に引きこもって暖かく過ごしてます。快適です。外出たくない。

というわけで、今日も外に出ずにできる素晴らしい~~暇つぶし~~コンテンツであるAtCoder Beginner Contest (abc) 166 C問題やっていきます。

言語はPython、提出はPyPyです。

C問題

C問題

Peaks

問題文

C - Peaks

展望台がN個存在します。
その中に良い展望台は何個ありますか？
ただし、良い展望台とは、その展望台に繋がっている展望台の中でどの展望台よりも高い物を指します。
という問題。

なんかこんな感じの問題をBFS（幅優先探索）とかDFS（深さ優先探索）とかの問題で見た気がする！！

でも、それらの探索方法について、詳しく知らないので、それっぽい感じの解き方で解きました。

方針として、
1. 展望台から道1本で行ける展望台(隣接してる展望台)を記録する。
2. 展望台の高さを、1でリストアップした展望台の高さと比較する。
3. 2の結果、他の全ての展望台より高ければ、その展望台はよい展望台である。
4. 1~3を全ての展望台について行う。(全探索)
という感じでACできました。

というわけで、コードを。

n,m = map(int,input().split())
h = list(map(int,input().split()))
map1 = []
ans = 0
for _ in range(n+1):
    map1.append(set())

for _ in range(m):
    a,b = map(int,input().split())
    map1[a].add(b)
    map1[b].add(a)    

for i in range(1,n+1):
    kijun = h[i-1]
    map1[i] = list(map1[i])
    for j in range(len(map1[i])):
        if kijun <= h[map1[i][j]-1]:
            break
    else:
        ans += 1        


print(ans)

解説を。

map1 = []
for _ in range(n+1):
    map1.append(set())

for _ in range(m):
    a,b = map(int,input().split())
    map1[a].add(b)
    map1[b].add(a)

この問題の肝その１

ここでは、各展望台について、隣接している展望台（比較対象）について記録しています。

N = 4の時、
map1 = [[],[],[],[],[]]
として、
map1[i]に展望台iと隣接している展望台の番号を入れていく。
道1で、展望台1と4が繋がっているのであれば、
map1 = [[],[4],[],[],[1]]
というように、
map1[1] = 4
map1[4] = 1
を返すようにする。

という感じです。また、その過程で、map1[i]に要素を追加する時、重複を許す（3が2回入るとか）と面倒なので、setを使ってます。
量が多くなると、計算量が馬鹿にならないので、大事。

for i in range(1,n+1):
    kijun = h[i-1]
    map1[i] = list(map1[i])
    for j in range(len(map1[i])):
        if kijun <= h[map1[i][j]-1]:
            break
    else:
        ans += 1

この問題の肝その２

全探索部分です。

やってることは単純で、展望台iと隣接している展望台の高さと比較して、展望台iが全てにおいて高ければ、答えを+1していくだけです。

展望台iの高さをkijunとしてます。
map1[i]をlistに変換しているのは、そうしないとmap[i][j]を取り出せないからです。
そして、kijunと、他の展望台の高さを比較していくのですが、高さを表すhだけ、0始まりで、他のは1始まりなので、注意。
比較して、kijunの方が低い(同じを含む)場合は、ループを打ち切り。
ループが完遂される = 他の展望台より高い
なので、elseで、ループが完遂された時にansを+1していく。