概要

各観測地点について、連続する \(K\) 日間の「最大値と最小値の差」の最大値を求め、それが閾値 \(T\) 以上である地点の個数を数える問題です。

考察

素朴なアプローチ

各観測地点で、すべての連続 \(K\) 日間の区間（全部で \(M - K + 1\) 個）について、その区間の最大値・最小値を毎回計算する方法が考えられます。

しかし、1つの区間の最大値・最小値を求めるのに \(O(K)\) かかるため、1地点あたり \(O(M \times K)\)、全体で \(O(N \times M \times K)\) となります。\(M, K\) が最大 \(10^5\)、\(N \times M \leq 2 \times 10^6\) の制約では、これは間に合いません。

高速化の鍵：スライディングウィンドウ最大・最小

ポイントは、幅 \(K\) の窓を1つずつずらしながら、区間内の最大値・最小値を効率的に更新することです。

ここで「スライディングウィンドウ最大値（最小値）」というテクニックを使うと、各区間の最大値・最小値を全体で \(O(M)\) 時間で求められます。これにより、1地点あたり \(O(M)\) で処理できます。

早期終了

さらに、ある区間で差が \(T\) 以上になった時点で、その地点は「条件を満たす」と確定するので、それ以降の区間を調べる必要はありません。ループを打ち切ることで無駄な計算を省けます（最悪計算量は変わりませんが実用上高速になります）。

アルゴリズム

スライディングウィンドウ最大値・最小値は、単調デック（双方向キュー） を使って実現します。

最大値を求めるデック maxd の動きを説明します（インデックスを格納します）。

1. 新しい要素 \(v = S_{i,j}\) を追加するとき、デックの末尾にある要素のうち \(v\) 以下のものは、今後二度と最大値になりえないので取り除きます（\(v\) の方が新しくて大きいから）。
2. その後、\(j\) を末尾に追加します。これによりデックは値が単調に減少する状態が保たれ、先頭が常に窓内の最大値を指します。
3. 窓の範囲（直近 \(K\) 個）から外れたインデックスが先頭にあれば、先頭から取り除きます。

最小値を求めるデック mind も同様で、「以上」を取り除く（単調増加を保つ）ようにします。

各日 \(j\) について、\(j \geq K-1\)（窓がちょうど \(K\) 日分そろった）とき、 $\( S_{i,\text{maxd先頭}} - S_{i,\text{mind先頭}} \)\( がその区間の最大値と最小値の差です。これが \)T$ 以上になればその地点をカウントし、ループを抜けます。

具体例

例えば気温が [3, 1, 4, 1, 5]、\(K=3\) のとき：

• 区間 [3,1,4] → 最大4, 最小1, 差3
• 区間 [1,4,1] → 最大4, 最小1, 差3
• 区間 [4,1,5] → 最大5, 最小1, 差4

差の最大値は4となります。\(T \leq 4\) ならこの地点はカウントされます。デックを使えば、各区間の最大・最小を窓をずらすだけで \(O(1)\) ずつ更新できます。

計算量

各観測地点について、各インデックスはデックに1回追加され、高々1回削除されるだけなので、1地点あたり \(O(M)\) で処理できます。

• 時間計算量: \(O(N \times M)\)（制約より \(N \times M \leq 2 \times 10^6\) なので十分高速）
• 空間計算量: \(O(M)\)（1地点分のデータとデックを保持）

実装のポイント

• デックにはインデックスを格納する：値そのものではなくインデックスを入れることで、「窓の範囲から外れたか」を判定できます。lim = j - K より小さい（または等しい）インデックスは窓外として先頭から取り除きます。

• 入力の高速読み込み：\(N \times M\) が最大 \(2 \times 10^6\) と大きいため、sys.stdin.buffer.read() で一括読み込みし、split() でまとめて分割すると高速です。1要素ずつ input() で読むと TLE の危険があります。

• 早期終了：条件を満たした時点で break することで、無駄な計算を避けられます。

• 整数比較で十分：気温は整数なので差も整数となり、誤差を気にする必要はありません。

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    count = 0
    for _ in range(N):
        row = data[idx:idx+M]
        idx += M
        arr = [int(x) for x in row]
        maxd = deque()  # decreasing
        mind = deque()  # increasing
        found = False
        for j in range(M):
            v = arr[j]
            while maxd and arr[maxd[-1]] <= v:
                maxd.pop()
            maxd.append(j)
            while mind and arr[mind[-1]] >= v:
                mind.pop()
            mind.append(j)
            lim = j - K
            if maxd[0] <= lim:
                maxd.popleft()
            if mind[0] <= lim:
                mind.popleft()
            if j >= K-1:
                if arr[maxd[0]] - arr[mind[0]] >= T:
                    found = True
                    break
        if found:
            count += 1
    print(count)

main()

---

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