概要

\(N\) 個の地点の高さ \(H_i\) が与えられたとき、同じ高さが \(K\) 個以上連続している箇所（平坦な区間）が存在するかどうかを判定する問題です。

考察

この問題を解くために、まずは「平坦な区間」の条件を整理します。 ある地点から \(K\) 個連続して同じ高さであるということは、隣り合う要素が等しい状態が \(K-1\) 回連続して続いていると言い換えることができます。

素朴なアプローチ

すべての地点 \(l\) について、「地点 \(l\) から \(l+K-1\) までの \(K\) 個がすべて同じか？」を愚直にチェックする方法が考えられます。 しかし、この方法では各開始地点に対して最大 \(K\) 回の比較を行うため、最悪の場合の計算量は \(O(N \times K)\) となります。 制約では \(N, K \leq 2 \times 10^5\) であるため、計算回数が最大で \(4 \times 10^{10}\) 回程度になり、実行時間制限（通常 2秒程度）に間に合いません（TLEとなります）。

効率的なアプローチ

配列を先頭から一度だけ走査し、「現在、同じ高さが何個連続しているか」をカウントする変数（streak）を保持することで、効率的に判定できます。 - 前の地点と高さが同じなら、streak を \(1\) 増やす。 - 前の地点と高さが異なれば、streak を \(1\) にリセットする。 - 走査の途中で streak が \(K\) に達した瞬間、平坦な区間が存在すると判断できます。

この方法であれば、配列を 1 回確認するだけで済むため、高速に動作します。

アルゴリズム

1. 連続する数をカウントする変数 streak を \(1\) に初期化します。
2. \(K=1\) の場合は、どの地点も単体で「長さ 1 の平坦な区間」とみなせるため、即座に Yes を出力します。
3. \(i = 2\) から \(N\) までの地点を順番に確認します。
   • \(H_i = H_{i-1}\) ならば、streak を \(1\) 加算します。
   • \(H_i \neq H_{i-1}\) ならば、streak を \(1\) に戻します。
   • もし streak が \(K\) 以上になれば、その時点で Yes を出力して終了します。
4. 最後まで走査しても streak が \(K\) に達しなければ、No を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度ずつ確認するため、入力の数に対して線形な時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の高さをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(K=1\) の処理: ループに入る前に \(K=1\) のケースを個別に判定しておくと、ロジックがシンプルになります。

• 高速な入力: Python で \(N\) が大きい場合、input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できます。

• 比較の開始位置: 2番目の要素（インデックス 1）から前の要素と比較を始めることで、範囲外アクセスを防ぎつつスムーズに走査できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # これにより、N, K および H_1, ..., H_N が一つのリストに格納される
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # 地点の数 N と平坦な区間の長さ K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # K が 1 の場合、任意の 1 地点が平坦な区間の定義を満たす
    # 制約より 1 <= K <= N なので、N >= 1 であり必ず存在する
    if k == 1:
        print("Yes")
        return
    
    # 各地点の高さを整数リストとして取得
    # input_data[2] から input_data[n+1] までが H_1 から H_N に対応する
    h = list(map(int, input_data[2:]))
    
    # 連続する同じ高さの地点の数をカウントする変数
    streak = 1
    
    # 2番目の地点から順に前の地点と高さを比較する
    for i in range(1, n):
        if h[i] == h[i-1]:
            # 前の地点と同じ高さであればカウントを増やす
            streak += 1
            # カウントが K に達すれば、平坦な区間が存在する
            if streak >= k:
                print("Yes")
                return
        else:
            # 高さが異なればカウントを 1 にリセットする
            streak = 1
    
    # すべての地点を確認しても K 連続が見つからなかった場合
    print("No")

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-thinking によって生成されました。