概要

\(N\) 日間の気温データの中で、基準となる温度 \(K\) 以上の「猛暑日」が連続して続いた最大の日数を求める問題です。

考察

この問題で重要なのは、「猛暑日が途切れた瞬間に、それまでの連続記録をリセットする」という考え方です。

例えば、気温が [30, 32, 25, 31, 33, 34, 28] で \(K=30\) の場合を考えてみます。 1. 1日目(30)・2日目(32)は \(K\) 以上なので、連続日数は 2 になります。 2. 3日目(25)は \(K\) 未満なので、ここで連続記録が途切れます。連続日数を 0 に戻します。 3. 4日目〜6日目は \(K\) 以上なので、連続日数は 3 まで伸びます。 4. 7日目(28)で再び途切れます。

この過程で記録された連続日数のうち、最大値である 3 が答えとなります。

\(N\) が最大で \(10^6\) と非常に大きいため、二重ループを使って「全ての開始地点と終了地点の組み合わせ」を試すと \(O(N^2)\) の計算量となり、実行時間制限（TLE）に間に合いません。データを先頭から 1 回だけ走査する \(O(N)\) の効率的なアプローチが必要です。

アルゴリズム

1. 最大の連続日数を保持する変数 max_streak と、現在の連続日数を保持する変数 current_streak を \(0\) で初期化します。
2. 気温データを 1 日目から順番に確認します。
   • もし、その日の気温が \(K\) 以上であれば、current_streak を \(1\) 増やします。
   • 増やした後の current_streak が max_streak よりも大きければ、max_streak を更新します。
   • もし、その日の気温が \(K\) 未満であれば、連続が途切れたことを意味するため current_streak を \(0\) にリセットします。
3. 全ての日数を確認し終えたあとの max_streak の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • データを 1 回だけ先頭から末尾までスキャンするため、日数 \(N\) に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力された気温データをリストとして保持するために \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(10^6\) と大きいため、Python の標準的な input() を繰り返すよりも、sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できます。

• 最大値の更新タイミング: 猛暑日が続いている間、常に max_streak を更新するように実装することで、最後に猛暑日が続いたままデータが終わる場合でも正しく計算できます。

  ソースコード

import sys

def main():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 日数 N と基準気温 K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各日の気温 A_i を取得（イテレータとして扱うことでメモリ効率を上げます）
    temperatures = map(int, input_data[2:])
    
    max_streak = 0
    current_streak = 0
    
    for temp in temperatures:
        if temp >= k:
            # 猛暑日の場合、現在の連続日数をインクリメント
            current_streak += 1
            # 最大値を更新
            if current_streak > max_streak:
                max_streak = current_streak
        else:
            # 非猛暑日の場合、連続日数をリセット
            current_streak = 0
            
    # 結果を出力
    print(max_streak)

if __name__ == '__main__':
    main()

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