概要

与えられた \(N\) 日間の気温データから、猛暑日（\(K\) 度以上）が連続する最長の日数を求める問題です。

考察

この問題は、猛暑日が連続する区間の長さの最大値を求めるものです。各日を順に見ていき、猛暑日が続く限りカウントを増やし、猛暑日でない日が来たらそこでカウントをリセットします。このようにして、連続する猛暑日の長さを逐次更新していくことで効率的に解くことができます。素朴なアプローチとして、すべての連続区間を調べ上げる方法も考えられますが、\(N\) が最大 \(10^6\) と大きいため、\(O(N^2)\) の方法では時間がかかりすぎます。そこで、1回の走査で解ける線形時間のアルゴリズムを用います。

アルゴリズム

1. 変数 current を0で初期化し、現在の連続猛暑日数を保持します。
2. 変数 max_streak を0で初期化し、これまでで最長の連続猛暑日数を保持します。
3. 各日の気温を順に調べます：
   • 気温が \(K\) 以上なら、current を1増やします。
   • そうでなければ、current が max_streak より大きければ max_streak を更新し、current を0にリセットします。
4. 最後に、最後の区間が猛暑日で終わっている場合に備え、ループ後に current と max_streak を比較して更新します。
5. max_streak を出力します。

このアルゴリズムは、配列を1回だけ走査するので効率的です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力データを保存するため）

実装のポイント

• 入力の読み込みは sys.stdin.read().split() を使って一度に読み、リストに格納します。これにより、大量の入力でも高速に処理できます。

• ループの最後で、最後の区間が猛暑日で終わっている場合の処理を忘れないようにします。ループ後に current と max_streak を比較して更新する必要があります。

• 猛暑日が一日もない場合は、max_streak の初期値が0のため、正しく0が出力されます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    max_streak = 0
    current = 0
    
    for temp in A:
        if temp >= K:
            current += 1
        else:
            if current > max_streak:
                max_streak = current
            current = 0
            
    if current > max_streak:
        max_streak = current
        
    print(max_streak)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。