概要

各観測地点について、長さ \(M\) の気温データから「連続する \(K\) 日間の最大値と最小値の差」の最大値（気温変動スコア）を求め、それが閾値 \(T\) 以上となる地点の数を数える問題です。

考察

まず、各観測地点ごとに独立に「気温変動スコア」を計算すればよいことがわかります。問題の本質は、1つの数列に対して すべての長さ \(K\) の連続区間（スライディングウィンドウ）における最大値と最小値 を効率よく求めることです。

素朴なアプローチの問題点

各区間ごとに愚直に最大値・最小値を計算すると、1区間あたり \(O(K)\)、区間は約 \(M\) 個あるので、1地点あたり \(O(MK)\) かかります。全地点では \(O(NMK)\) となり、\(N \times M \leq 2 \times 10^6\)、\(K\) が最大 \(10^5\) の制約では到底間に合いません。

解決のアイデア

ここで使えるのが スライディングウィンドウ最大値・最小値 のテクニックです。ウィンドウを左から右へ1つずつずらしていくとき、各ステップで「新しい要素が1つ入り、古い要素が1つ出る」だけです。この性質を利用すると、すべての区間の最大値・最小値を 線形時間 で求められます。

キーとなる観察は次の通りです。

• 最大値を求める際、ウィンドウ内のある要素 \(a\) より後ろに、\(a\) 以上の値 \(b\) が現れたら、\(a\) は二度と最大値になれない（\(b\) の方が新しく、かつ大きいから）。
• よって、そのような「将来役に立たない要素」を捨てながら、候補だけを管理すればよいです。

この管理に 両端キュー（deque） を使います。

アルゴリズム

最大値用と最小値用に、それぞれ deque を用意します。deque にはインデックスを格納します。

最大値用 deque（値が単調減少になるように保つ）

各新しい要素 \(j\) を追加するとき： 1. deque の末尾の要素の値が \(S_j\) 以下である限り、末尾を取り除く（それらは \(j\) が入ると不要になる）。 2. \(j\) を末尾に追加する。 3. ウィンドウの左端 \(j - K + 1\) より前のインデックスが先頭にあれば取り除く。

すると、deque の 先頭が常に現在のウィンドウの最大値 を指します。

最小値用 deque（値が単調増加になるように保つ）

不等号の向きを逆にすれば、同様に先頭が最小値を指します。

各地点について \(j \geq K-1\)（ウィンドウが完全に埋まった）時点で、最大値 - 最小値 を計算し、その地点での最大値（スコア）を更新します。最後に各地点のスコアが \(T\) 以上かを判定し、カウントします。

具体例

数列 \(S = [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\)

スコアは \(\max(3,3,4) = 4\) となります。deque を使うと、これらを左から1回スキャンするだけで求められます。

計算量

各要素は deque に高々1回入り、高々1回出るため、1地点あたりの処理は \(O(M)\) です。

• 時間計算量: \(O(N \times M)\)（全体で \(O(NM) \leq 2 \times 10^6\) なので高速）
• 空間計算量: \(O(M)\)（数列と deque を地点ごとに使い回す）

実装のポイント

• オーバーフローに注意：気温は \(-10^9 \leq S_{i,j} \leq 10^9\) なので、最大値と最小値の差は最大 \(2 \times 10^9\) となり int の範囲を超えます。スコアや差、閾値 \(T\) は long long（64bit整数）で扱う必要があります。

• deque を配列で実装：標準の std::deque でも実装できますが、本コードでは vector<int> と head/tail のインデックスで両端キューを実現し、地点ごとに maxHead, maxTail などをリセットすることで高速化しています。要素数は最大 \(M\) なので配列サイズも \(M\) で十分です。

• 高速入力：\(N \times M\) が最大 \(2 \times 10^6\) で入力量が大きいため、fread でまとめて読み込み、自前のパーサで整数を読む工夫をしています。cin のままだと入力で時間を取られる恐れがあります。

• ウィンドウ確定のタイミング：\(j \geq K-1\) になって初めてウィンドウ幅が \(K\) に達するので、それ以降でのみスコアを更新します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M, K;
    long long T;
    
    // fast input
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    auto readInt = [&]() -> long long {
        while(pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if(pos < len && buf[pos] == '-'){ neg = true; pos++; }
        long long x = 0;
        while(pos < len && buf[pos] >= '0' && buf[pos] <= '9'){
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };
    
    N = (int)readInt();
    M = (int)readInt();
    K = (int)readInt();
    T = readInt();
    
    vector<long long> S(M);
    // deque storing indices
    vector<int> maxDq(M), minDq(M);
    
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++) S[j] = readInt();
        
        long long score = LLONG_MIN;
        int maxHead = 0, maxTail = 0; // [maxHead, maxTail)
        int minHead = 0, minTail = 0;
        
        for(int j = 0; j < M; j++){
            // add j to max deque (decreasing)
            while(maxTail > maxHead && S[maxDq[maxTail-1]] <= S[j]) maxTail--;
            maxDq[maxTail++] = j;
            // add j to min deque (increasing)
            while(minTail > minHead && S[minDq[minTail-1]] >= S[j]) minTail--;
            minDq[minTail++] = j;
            
            // remove out of window from front
            int windowStart = j - K + 1;
            while(maxTail > maxHead && maxDq[maxHead] < windowStart) maxHead++;
            while(minTail > minHead && minDq[minHead] < windowStart) minHead++;
            
            if(j >= K - 1){
                long long diff = S[maxDq[maxHead]] - S[minDq[minHead]];
                if(diff > score) score = diff;
            }
        }
        
        if(score >= T) count++;
    }
    
    printf("%d\n", count);
    return 0;
}

---

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