🙆‍♀️

Kickstart2020 RoundB: Bike Tour

2021/05/15に公開

Python

kickstart

tech

問題

各要素が山の高さ（i番目の要素は $H_i$ とする）であるN個のチェックポイントが与えられたとき、ピークとなる $H_i$ の数をカウントする。ピークとなる条件は、

最初、またはN番目の要素ではない
一つ前と一つ後の高さよりも高い

実装

2番目の要素からN-1番目の要素について、上記の二つ目の条件をチェックすれば良い。このときの条件チェックは、配列要素の比較でO(1)で実行でき、トータルの計算量はO(N)。

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    ckpts = list(map(int, input().split()))
    res = 0
    for i in range(1, N - 1):
        if ckpts[i - 1] < ckpts[i] and ckpts[i] > ckpts[i + 1]:
            res += 1
    print('Case #{}: {}'.format(t, res))

問題

実装

Discussion