概要

この問題は、数列 \(H_1, H_2, \ldots, H_N\) の中に、同じ値が連続して \(K\) 回以上現れる場所があるかを判定する問題です。
左から順に見て、同じ高さが何回連続しているかを数えれば、効率よく判定できます。

考察

平坦な区間とは、長さ \(K\) の連続区間の中ですべての値が等しい区間のことです。

つまり、ある区間が平坦であるための条件は

\(H_l = H_{l+1} = \cdots = H_{l+K-1}\)

です。
これは言い換えると、同じ値が連続して \(K\) 個並んでいる場所があるかを調べればよい、ということになります。

素朴な方法

各始点 \(l\) について、区間 \([l, l+K-1]\) の値がすべて等しいかを毎回確認する方法が考えられます。

しかしこの方法では、各区間の確認に最大 \(K\) 回比較が必要で、始点は最大 \(N-K+1\) 個あるので、計算量はおおよそ

\(O(NK)\)

になります。

制約では \(N \leq 2 \times 10^5\) なので、\(K\) も同程度になる可能性があり、この方法では間に合いません。

重要な気づき

必要なのは「長さちょうど \(K\) の区間」を全部調べることではなく、
同じ値が何個連続しているかを追跡することです。

たとえば

\([5, 5, 5, 2, 2, 7, 7, 7, 7]\)

という列なら、連続個数は

• \(5\) が \(3\) 個連続
• \(2\) が \(2\) 個連続
• \(7\) が \(4\) 個連続

となります。
この中に \(K\) 以上の連続個数があれば、平坦な区間が存在します。

どう解決するか

左から順に値を読みながら、

• 直前の値 prev
• その値が何回連続しているか cnt

を持っておけば十分です。

新しく読んだ値 x について

• x == prev なら cnt += 1
• x != prev なら連続が途切れるので prev = x, cnt = 1

とします。

この途中で cnt >= K になったら、長さ \(K\) の平坦な区間が存在することが確定するので、すぐに Yes を出力できます。

アルゴリズム

1. \(K = 1\) なら、どの 1 点だけを見ても高さはすべて等しいので、必ず平坦な区間が存在する。よって Yes。
2. 最初の高さを読み込み、prev に入れる。
3. cnt = 1 として、同じ高さの連続個数を表す。
4. 残りの \(N-1\) 個の高さを順に読む。
   • 今読んだ値を x とする。
   • x == prev なら cnt += 1
     • もし cnt >= K なら Yes を出力して終了。
   • x != prev なら
     • prev = x
     • cnt = 1
5. 最後まで cnt >= K にならなければ No。

例

たとえば

\(N=7, K=3\)
高さ列が

\([4, 4, 1, 1, 1, 2, 2]\)

だとします。

• 最初の \(4\) で cnt = 1
• 次の \(4\) で cnt = 2
• 次の \(1\) で値が変わるので cnt = 1
• 次の \(1\) で cnt = 2
• 次の \(1\) で cnt = 3

ここで cnt >= K なので、Yes です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• \(K = 1\) は必ず条件を満たすので、最初に特別扱いすると簡潔です。

• 配列全体を保存しなくても、直前の値と連続個数だけあれば判定できます。

• 値が変わったときは、連続個数を \(1\) に戻すことを忘れないようにします。

• 今回の実装は入力を 1 個ずつ読みながら処理しており、メモリ効率も良いです。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())

    if K == 1:
        print("Yes")
        return

    prev = int(input())
    cnt = 1

    for _ in range(N - 1):
        x = int(input())
        if x == prev:
            cnt += 1
            if cnt >= K:
                print("Yes")
                return
        else:
            prev = x
            cnt = 1

    print("No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。