概要

長さ \(N\) の数列の中に、同じ値が \(K\) 個以上連続する箇所があるかどうかを判定する問題です。

考察

重要な気づき

まず素朴に考えると、すべての開始位置 \(l\) について区間 \([l, l+K-1]\) の要素が全部同じかを確認する方法があります。しかしこれは各区間で最大 \(K\) 回の比較が必要で、全体で \(O(NK)\) となり、\(N\) や \(K\) が大きい場合に非効率です。

ここで重要な気づきは、「同じ値が何個連続しているか」をカウントしながら1回走査すれば十分だということです。

具体例で理解する

例えば \(N = 7\), \(K = 3\), 高さが [3, 3, 5, 5, 5, 5, 2] の場合を考えます。

地点 \(i\)	\(H_i\)	連続カウント
1	3	1
2	3	2
3	5	1（リセット）
4	5	2
5	5	3 ← \(K\) 以上！

地点 5 の時点でカウントが \(3 \geq K\) になるので、平坦な区間が存在すると判定できます。

\(K = 1\) の特殊ケース

\(K = 1\) の場合、長さ1の区間はどの地点でも平坦なので、\(N \geq 1\) であれば必ず Yes です。

アルゴリズム

1. \(K = 1\) なら即座に Yes と答える。
2. そうでなければ、変数 count を \(1\) に初期化し、地点 \(2\) から地点 \(N\) まで順に走査する。
3. 地点 \(i\) の高さが地点 \(i-1\) と同じなら count を \(1\) 増やす。異なればリセット（count = 1）。
4. count が \(K\) 以上になった時点で平坦な区間が見つかったので Yes を出力して終了。
5. 最後まで見つからなければ No を出力する。

この方法は「ランレングス」的な考え方で、同じ値の連続する長さ（ラン）を追跡しています。

計算量

• 時間計算量: \(O(N)\) — 配列を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の配列を保持するため（走査用の変数は \(O(1)\)）

実装のポイント

• count の初期値は \(1\): 地点1自体が長さ1の連続を形成しているため、\(0\) ではなく \(1\) から始めます。

• 隣接比較でリセットを忘れない: \(H_i \neq H_{i-1}\) のときに count = 1 にリセットします。\(0\) にしてしまうと正しく動きません（現在の地点自体が新たな連続の始まりなので \(1\)）。

• 早期終了: count >= K になった瞬間に break することで、無駄な走査を省けます。ただし最悪計算量は変わりません。

  ソースコード

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

count = 1
found = False
if K == 1:
    found = True
else:
    for i in range(1, N):
        if H[i] == H[i-1]:
            count += 1
            if count >= K:
                found = True
                break
        else:
            count = 1

print("Yes" if found else "No")

---

この解説は claude4.6opus-thinking によって生成されました。