概要

各観測地点について、長さ \(K\) の連続区間ごとの「最大値 \(-\) 最小値」を調べ、その最大値が \(T\) 以上になる地点の数を求めます。

考察

ある観測地点の気温データを \(S_1, S_2, \ldots, S_M\) とします。

求めたいのは、すべての長さ \(K\) の区間について

\[ \max(S_l, \ldots, S_{l+K-1}) - \min(S_l, \ldots, S_{l+K-1}) \]

を計算し、その中に \(T\) 以上のものがあるかどうかです。

つまり、各観測地点について

長さ \(K\) の区間の中に、最大値と最小値の差が \(T\) 以上になるものが存在するか

を判定すればよいです。

素朴に各区間ごとに最大値・最小値を計算すると、1 つの観測地点あたり

\[ O((M-K+1)K) \]

かかります。

制約では \(N \times M \leq 2 \times 10^6\) ですが、\(K\) は最大で \(10^5\) なので、この方法では間に合いません。

そこで、長さ \(K\) のスライドする区間について、最大値と最小値を高速に管理する必要があります。

この問題では、単調キューを使うことで、各観測地点を \(O(M)\) で処理できます。

アルゴリズム

各観測地点ごとに、左から右へ気温データを見ていきます。

現在見ている位置を \(i\) とすると、長さ \(K\) の現在の区間は

\[ [i-K+1, i] \]

です。

この区間の最大値と最小値を高速に求めるために、次の 2 つのキューを用意します。

• 最大値用キュー qmax
  • 値が大きい順に並ぶように管理する
  • 先頭が現在の区間の最大値
• 最小値用キュー qmin
  • 値が小さい順に並ぶように管理する
  • 先頭が現在の区間の最小値

キューには値そのものではなく、配列の添字を入れます。

これは、区間の外に出た要素を判定するためです。

最大値用キューの更新

新しい値 \(x = S_i\) を追加するとき、キューの末尾にある値が \(x\) 以下なら、それらは今後最大値になる可能性がありません。

そのため、末尾から削除します。

その後、添字 \(i\) を追加します。

これにより、キュー内の値は常に大きい順になります。

最小値用キューの更新

同様に、新しい値 \(x = S_i\) を追加するとき、キューの末尾にある値が \(x\) 以上なら削除します。

その後、添字 \(i\) を追加します。

これにより、キュー内の値は常に小さい順になります。

区間外の要素を取り除く

現在の区間は \([i-K+1, i]\) なので、添字が

\[ i-K \]

以下のものは区間外です。

そのような添字がキューの先頭にあれば、先頭を進めて削除します。

判定

\(i \geq K-1\) になれば、長さ \(K\) の区間が完成しています。

そのとき、

• 最大値は a[qmax[hmax]]
• 最小値は a[qmin[hmin]]

なので、

\[ a[qmax[hmax]] - a[qmin[hmin]] \geq T \]

なら、その観測地点は条件を満たします。

1 つでも条件を満たす区間が見つかれば、その観測地点は答えに数えられるので、それ以上その行を調べる必要はありません。

計算量

• 時間計算量: \(O(NM)\)
• 空間計算量: \(O(M)\)

各要素は最大値用キュー・最小値用キューにそれぞれ高々 1 回追加され、高々 1 回削除されます。

したがって、各観測地点あたり \(O(M)\) で処理できます。

実装のポイント

このコードでは、いくつかの場合を先に処理しています。

\(T = 0\) の場合

最大値と最小値の差は常に \(0\) 以上です。

したがって、すべての観測地点が条件を満たすので、答えは \(N\) です。

\(K = 1\) の場合

長さ \(1\) の区間では、最大値と最小値は同じなので差は必ず \(0\) です。

ただし \(T = 0\) の場合はすでに処理済みなので、ここでは \(T > 0\) です。

よって、条件を満たす観測地点は存在せず、答えは \(0\) です。

\(K = M\) の場合

区間は全体 1 つだけです。

そのため、各観測地点について単純に

\[ \max(a) - \min(a) \]

を計算すれば十分です。

キューの実装

Python の collections.deque を使うこともできますが、このコードでは高速化のために配列と先頭・末尾のポインタでキューを実装しています。

• hmax, tmax: 最大値用キューの先頭・末尾
• hmin, tmin: 最小値用キューの先頭・末尾

配列 qmax, qmin には添字を保存し、実際の値は a[添字] で参照しています。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K, T = map(int, input().split())

    if T == 0:
        print(N)
        return

    if K == 1:
        print(0)
        return

    ans = 0

    if K == M:
        for _ in range(N):
            a = list(map(int, input().split()))
            if max(a) - min(a) >= T:
                ans += 1
        print(ans)
        return

    qmax = [0] * M
    qmin = [0] * M
    k1 = K - 1

    for _ in range(N):
        a = list(map(int, input().split()))

        hmax = tmax = 0
        hmin = tmin = 0

        for i, x in enumerate(a):
            while tmax > hmax and a[qmax[tmax - 1]] <= x:
                tmax -= 1
            qmax[tmax] = i
            tmax += 1

            while tmin > hmin and a[qmin[tmin - 1]] >= x:
                tmin -= 1
            qmin[tmin] = i
            tmin += 1

            limit = i - K
            if qmax[hmax] <= limit:
                hmax += 1
            if qmin[hmin] <= limit:
                hmin += 1

            if i >= k1 and a[qmax[hmax]] - a[qmin[hmin]] >= T:
                ans += 1
                break

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。