🍣

Kickstart 2020 Round D: Record Breaker

2021/08/19に公開

Python

kickstart

tech

問題

N個の要素からなる配列が与えられる。i番目の要素 $V_i$ は、テーマパークの来場者数を表す。下記の条件を満たす日をrecord breaking dayとすると、何日あるかを計算する。

当日の来場者数が、前日までのどの日の来場者よりも多い
最終日か、当日の来場者が、翌日の来場者よりも多い

アルゴリズム

現在注目している要素が最終日ではない場合、翌日の来場者との比較は $\rm{O(1)}$ で実行可能。注目日以前の全ての来場者との比較をすると $\rm{O（N）}$ となってしまうが、全ての日を比較する必要はなくて、前日までの来場者数の最大値に対して比較すれば $\rm{O(1)}$ で処理出来る。全体として $\rm{O(N）}$ の計算量でカウントすることができる。

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    visitors = list(map(int, input().split(' ')))
    prev_record = 0
    res = 0
    for i in range(N):
        greater_than_prev = i == 0 or visitors[i] > prev_record
        greater_than_next = i == N - 1 or visitors[i] > visitors[i + 1]
        res = res + 1 if greater_than_prev and greater_than_next else res
        prev_record = max(prev_record, visitors[i])
    print('Case #{}: {}'.format(t, res))

問題

アルゴリズム

Discussion