概要

「長さ \(K\) の連続区間で、全ての高さが同じ場所があるか」を判定する問題です。
配列を左から1回見るだけで、同じ値が何個連続しているかを数えれば判定できます。

考察

平坦な区間とは、連続する \(K\) 個がすべて同じということです。
これは言い換えると、「同じ高さが \(K\) 回以上連続する部分があるか」です。

例えば
\(H = [3,3,3,2,2,5]\), \(K=3\) なら、先頭の 3,3,3 が条件を満たすので Yes です。

素朴な方法

各開始位置 \(l\) ごとに、長さ \(K\) の区間 \(H_l \sim H_{l+K-1}\) が全部同じか確認する方法が考えられます。
この場合、区間の数は約 \(N\) 個、各区間の確認に最大 \(K\) 回かかるため、\(O(NK)\) になります。
\(N=2\times10^5\) では間に合わない可能性が高いです。

改善の発想

配列を左から見ながら「現在の連続長」を持てばよいです。

• 前の値と同じなら連続長 run を \(+1\)
• 違うなら run=1 にリセット
• 途中で run >= K になったら即 Yes

これなら1回の走査で終わります。

アルゴリズム

1. \(N, K\) と配列 \(H\) を読む。
2. もし \(K=1\) なら、どの1点区間も平坦なので即 Yes。
3. run=1 で開始。
4. \(i=1\) から \(N-1\) まで順に見る。
   • もし \(H_i = H_{i-1}\) なら run += 1
   • そうでなければ run = 1
   • run >= K なら Yes を出力して終了
5. 最後まで見つからなければ No。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（実装では配列 \(H\) を保持しているため）

実装のポイント

• K==1 は必ず Yes になるので先に処理すると分かりやすいです。

• 連続長 run の初期値は1（要素1個だけでも同じ値が1個連続している）にします。

• 条件を満たした時点で早期 return すると無駄な走査を防げます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = [int(input()) for _ in range(N)]

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

    run = 1
    for i in range(1, N):
        if H[i] == H[i - 1]:
            run += 1
            if run >= K:
                print("Yes")
                return
        else:
            run = 1

    print("No")

if __name__ == "__main__":
    main()

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