🍣

Kicstart2020 RoundC: Countdown

2021/06/12に公開

問題

長さが $m$ で、 $m,m-1,m-2,...,2,1$ のsubarrayをm-countdownと呼ぶ。この時、N個の要素を含む配列とKが与えられた時に、幾つのK-countdownが含まれているかを求める。
$2 \leq K \leq N$ 、Test set1では $2 \leq N \leq 1000$ 、Test set2では高々10ケースで $2 \leq N \leq 2 \times 10^5$ で残りはTest set1と同じサイズ。

アルゴリズムと実装

各要素を一つずつ走査して、previousの要素よりも１小さくなっているかを確認し、Trueの場合には連続していることを表すカウンタを1つ増やす。Falseの場合にはカウンタを０に戻す。
現在の要素が1で、かつカウンタが少なくともK-1になっていればK-countdownが見つかったとして、結果をインクリメントする。（開始位置ではカウンタは０）

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

問題

アルゴリズムと実装

Discussion