概要

この問題は、各観測地点における過去 \(M\) 日間の気温データから、「長さ \(K\) の連続する区間における（最大値 - 最小値）が \(T\) 以上になる場所が1つでも存在するか」を判定する問題です。

すべての観測地点についてこの判定を行い、条件を満たす観測地点の総数を求めます。

考察

素朴なアプローチとその限界

最も単純な方法は、各観測地点について、長さ \(K\) の区間をすべて愚直に調べる方法です。 区間の開始位置は \(M - K + 1\) 通りあり、それぞれの区間内で最大値と最小値を求めるのに \(O(K)\) の時間がかかります。 この場合、1つの観測地点あたりの計算量は \(O((M - K) \times K)\) となります。

最悪のケース（例えば \(M = 10^5, K = 5 \times 10^4\)）では、1つの観測地点につき約 \(2.5 \times 10^9\) 回の計算が必要になり、これが \(N\) 地点分あるため、実行時間制限（通常2秒）に到底間に合わず TLE（実行時間制限超過） になってしまいます。

効率的なアプローチ

区間を右に1つスライドさせるとき、区間に入る要素は1つ、出ていく要素も1つだけです。この性質を利用して、区間内の最大値・最小値を効率的に更新していく必要があります。

これは「スライド最小値（最大値）」と呼ばれる有名な問題であり、両端キュー（deque）を用いることで、各観測地点のデータを左から右へ1回走査するだけ（\(O(M)\)）で解くことができます。

アルゴリズム

スライド最大値・最小値アルゴリズム

両端キュー（deque）を用いて、常に「現在の区間（長さ \(K\)）に含まれる要素」かつ「値が単調減少（または単調増加）するようなインデックスの列」を保持します。

ここでは最大値を求めるための max_dq の動作を説明します（最小値も不等号が逆になるだけで同様です）。

1. 新しい要素 \(S[j]\) の追加: キューの末尾にある要素を順に見て、その値が \(S[j]\) 以下である限り、それらをキューから取り除きます（pop）。 なぜなら、新しく入ってきた \(S[j]\) の方が値が大きく、かつ \(S[j]\) の方が長生きするため、それ以前の \(S[j]\) 以下の要素が今後区間内の最大値になることは絶対にないからです。その後、新しいインデックス \(j\) を末尾に追加します。
2. 古い要素の削除: キューの先頭にあるインデックスが、現在の区間の範囲外（\(j - K\) 以下）になった場合、先頭から取り除きます（popleft）。
3. 最大値の取得: 上記の操作を行うことで、キューの先頭（max_dq[0]）には常に現在の区間内での最大値のインデックスが格納されます。

具体例（\(K=3\), 配列 \(S = [2, 5, 3, 1]\) の場合）

• \(j=0\) （値: \(2\)）: max_dq は [0] になります。
• \(j=1\) （値: \(5\)）: 末尾の \(2\)（インデックス \(0\)）は \(5\) 以下なので取り除かれ、max_dq は [1] になります。
• \(j=2\) （値: \(3\)）: \(3\) は末尾の \(5\) より小さいのでそのまま追加され、max_dq は [1, 2] になります。
  • この時点で区間の長さが \(K=3\) に達します。現在の区間 [2, 5, 3] の最大値は S[max_dq[0]] = S[1] = \(5\) です。
• \(j=3\) （値: \(1\)）: \(1\) を追加して max_dq は [1, 2, 3] になりますが、先頭のインデックス \(1\) は区間外（\(3 - 3 = 0\) 以下ではないが、次のステップで外れる）になります。

この一連の操作を最大値用と最小値用の2つの deque で同時に行い、各ステップで (最大値) - (最小値) >= T が成り立つかを判定します。

計算量

• 時間計算量: \(O(N \times M)\) 各観測地点において、長さ \(M\) の配列の各要素は deque に「高々1回追加され、高々1回削除される」だけです。したがって、1つの観測地点あたりの処理は \(O(M)\) で行えます。 これを \(N\) 回繰り返すため、全体の計算量は \(O(N \times M)\) となり、制約の \(N \times M \le 2 \times 10^6\) に対して十分高速に動作します。

• 空間計算量: \(O(N \times M)\) 入力の気温データをすべて保持するために \(O(N \times M)\) のメモリを使用します。deque のサイズは最大でも \(K\) であるため、追加のメモリは極めてわずかです。

実装のポイント

1. 高速な入出力: Pythonでは入力行数が多くなる可能性があるため、sys.stdin.read().split() を用いてすべての入力を一度に読み込み、数値リストに変換することで、入出力にかかる時間を大幅に削減しています。

2. 早期終了（枝刈り）: ある観測地点において、条件を満たす区間が1つでも見つかった（ok = True になった）時点で、その地点の探索を break して次の観測地点の処理に移っています。これにより、最悪ケース以外での実行時間をさらに短縮できます。

   ソースコード

import sys
from collections import deque


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    all_ints = list(map(int, input_data))
    N, M, K, T = all_ints[:4]

    ans = 0
    start_idx = 4

    for i in range(N):
        S = all_ints[start_idx : start_idx + M]
        start_idx += M

        max_dq = deque()
        min_dq = deque()
        ok = False

        for j in range(M):
            val = S[j]

            # max_dq の更新
            while max_dq and S[max_dq[-1]] <= val:
                max_dq.pop()
            max_dq.append(j)
            if max_dq[0] <= j - K:
                max_dq.popleft()

            # min_dq の更新
            while min_dq and S[min_dq[-1]] >= val:
                min_dq.pop()
            min_dq.append(j)
            if min_dq[0] <= j - K:
                min_dq.popleft()

            if j >= K - 1:
                if S[max_dq[0]] - S[min_dq[0]] >= T:
                    ok = True
                    break

        if ok:
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

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