概要

\(N\) 日間の気温データが与えられたとき、最高気温が \(K\) 以上の日（猛暑日）が連続する区間の最大長を求める問題です。典型的な「連続する条件を満たす要素の最長ラン」を求める問題です。

考察

問題の本質

配列の中で、ある条件（\(A_i \geq K\)）を満たす要素が連続している区間の最大長を求めたいです。

具体例で考える

例えば、\(N = 10\), \(K = 35\) で気温が以下のように与えられたとします：

33 36 37 35 34 38 39 40 36 33

各日が猛暑日かどうかを ○/× で表すと：

×  ○  ○  ○  ×  ○  ○  ○  ○  ×

連続する猛暑日の区間は「○○○」（長さ3）と「○○○○」（長さ4）の2つがあり、最大は 4 です。

素朴なアプローチ

すべての区間 \((l, r)\) を列挙して、その中がすべて猛暑日かどうかを確認する方法が考えられますが、区間の数は \(O(N^2)\) 個あり、各区間のチェックに \(O(N)\) かかると全体で \(O(N^3)\) になります。\(N \leq 10^6\) の制約では到底間に合いません。

効率的な解法：ランレングス的な走査

配列を先頭から1回走査しながら、「今、猛暑日が何日連続しているか」をカウンタで管理すれば十分です。

• 猛暑日なら、カウンタを \(+1\) する
• 猛暑日でなければ、カウンタを \(0\) にリセットする
• カウンタの値が過去最大を更新したら記録する

この方法なら配列を1回なめるだけで答えが求まります。

アルゴリズム

1. max_streak = 0（最大連続日数）、current_streak = 0（現在の連続日数）を初期化する。
2. \(i = 1, 2, \ldots, N\) について順に以下を行う：
   • \(A_i \geq K\) ならば current_streak を \(1\) 増やし、max_streak を max(max_streak, current_streak) で更新する。
   • \(A_i < K\) ならば current_streak を \(0\) にリセットする。
3. 最終的な max_streak を出力する。

猛暑日が一日もない場合、current_streak は一度も増えないので max_streak は初期値の \(0\) のまま出力されます。

計算量

• 時間計算量: \(O(N)\) — 配列を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の読み込みに配列を使用（走査自体に必要な追加メモリは \(O(1)\)）

実装のポイント

• 高速な入力: \(N\) が最大 \(10^6\) と大きいため、Python では sys.stdin.buffer.read() で一括読み込みを行い、split() でトークンに分割することで入力を高速化しています。input() を \(N\) 回呼ぶよりも大幅に速くなります。

• max 関数の回避: ループ内で max() 関数を毎回呼ぶ代わりに、if current_streak > max_streak という比較で更新しています。Python ではこの方が関数呼び出しのオーバーヘッドを避けられ、\(10^6\) 回のループでは差が出ることがあります。

• インデックスのずれに注意: 入力データは input_data[0] が \(N\)、input_data[1] が \(K\)、input_data[2] 以降が \(A_1, A_2, \ldots, A_N\) なので、\(A_i\) にアクセスするときは input_data[i + 2] となります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    max_streak = 0
    current_streak = 0
    
    for i in range(N):
        if int(input_data[i + 2]) >= K:
            current_streak += 1
            if current_streak > max_streak:
                max_streak = current_streak
        else:
            current_streak = 0
    
    print(max_streak)

main()

---

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