Edit

【pythonでABC166を解説】C - Peaks

問題概要

問題ページ

問題文

AtCoder丘陵には \(N\) 個の展望台があり、展望台 \(i\) の標高は \(H_i\) です。
また、異なる展望台どうしを結ぶ \(M\) 本の道があり、道 \(j\) は展望台 \(A_j\) と展望台 \(B_j\) を結んでいます。

展望台 \(i\) が良い展望台であるとは、展望台 \(i\) から一本の道を使って辿り着けるどの展望台よりも展望台 \(i\) の方が標高が高いことをいいます。
展望台 \(i\) から一本の道を使って辿り着ける展望台が存在しない場合も、展望台 \(i\) は良い展望台であるといいます。

良い展望台がいくつあるか求めてください。

制約

  • \(2 \leq N \leq 10^5\)
  • \(1 \leq M \leq 10^5\)
  • \(1 \leq H_i \leq 10^9\)
  • \(1 \leq A_i,B_i \leq N\)
  • \(A_i \neq B_i\)
  • 同じ展望台の組を結ぶ道が複数あることもある。
  • 入力中の値はすべて整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    h = list(map(int, input().rstrip('\n').split()))
    ls = [True] * n
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if h[a - 1] == h[b - 1]:
            ls[b - 1] = ls[a - 1] = False
        else:
            if h[a - 1] < h[b - 1]:
                a, b = b, a
            ls[b - 1] = False
    print(ls.count(True))


if __name__ == '__main__':
    solve()

プログラミング

-Edit