概要

各観測地点について、連続する \(K\) 日間の気温の最大値と最小値の差の最大値（気温変動スコア）を求め、そのスコアが閾値 \(T\) 以上である地点の数を数える問題です。

考察

この問題の要点は、「各地点の長さ \(K\) の区間における最大値と最小値をいかに高速に求めるか」です。

素朴なアプローチでは、すべての長さ \(K\) の区間について愚直に最大値と最小値を探します。1つの区間あたり \(K\) 回の比較が必要で、区間の数は \(M - K + 1\) 個あるため、1地点あたり \(O(M \times K)\) の計算量となります。制約の \(N \times M \leq 2 \times 10^6\) および \(K \leq M \leq 10^5\) のもとでは、最悪計算量が \(O(N \times M \times K)\) となりTLE（実行時間制限超過）になってしまいます。

これを解決するために、スライディングウィンドウ（Sliding Window）アルゴリズムを利用します。区間を1日ずつずらしていく際、新しく入ってくる要素と古い要素の関係をうまく利用することで、最大値と最小値を \(O(1)\) で更新し、1地点あたりの計算量を \(O(M)\) に削減できます。

アルゴリズム

スライディングウィンドウを用いて、長さ \(K\) の区間ごとの最大値と最小値を効率的に求めます。双方向キュー（deque）を使用します。

最大値を求める手順: 1. 要素のインデックスを格納するdequeを用意します。 2. 配列の先頭から順に要素を見ていきます。 3. dequeの末尾にあるインデックスが指す気温が、現在見ている気温以下であれば、そのインデックスは今後の最大値になることはないためdequeから削除します（これを現在の気温がdequeの末尾の気温より大きくなるまで繰り返します）。 4. 現在のインデックスをdequeの末尾に追加します。 5. dequeの先頭にあるインデックスが、現在のウィンドウ（幅 \(K\)）の範囲外であれば削除します。 6. ウィンドウの幅が \(K\) に達した時点で、dequeの先頭にあるインデックスが指す気温が、その区間の最大値となります。

最小値を求める手順も同様ですが、dequeの末尾にあるインデックスが指す気温が現在見ている気温以上であれば削除する、という点が異なります。

各地点で長さ \(K\) の区間ごとの最大値配列 max_vals と最小値配列 min_vals を作成したら、各区間での差 max_vals[j] - min_vals[j] を計算し、その最大値を気温変動スコアとします。スコアが閾値 \(T\) 以上であればカウントアップします。

計算量

• 時間計算量: \(O(N \times M)\) 各観測地点において、最大値・最小値のスライディングウィンドウ処理を \(O(M)\) で行います。全体で \(N\) 地点あるため \(O(N \times M)\) となります。
• 空間計算量: \(O(M)\) 各地点の気温データと、長さ \(K\) の区間の最大値・最小値を保持する配列をサイズ \(M\) 確保します。1地点分ずつ処理して使い回すため、全体で \(O(M)\) の空間計算量となります。

実装のポイント

• 気温の範囲が \(-10^9 \leq S_{i,j} \leq 10^9\) であり、最大値と最小値の差は最大で \(2 \times 10^9\) になります。32bit整数（int）の最大値（約 \(2.1 \times 10^9\)）を超える、またはギリギリになる可能性があるため、気温データやスコアの計算には64bit整数（long long 型）を使用する必要があります。

• 閾値 \(T\) も最大 \(2 \times 10^9\) であるため、long long 型で受け取ります。

• 入出力が多いため、cin.tie(0); ios::sync_with_stdio(false); を用いて入出力の高速化を行うと安全です。

  ソースコード

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, M, K;
    long long T;
    if (!(cin >> N >> M >> K >> T)) return 0;
    
    int ans = 0;
    for (int i = 0; i < N; i++) {
        vector<long long> S(M);
        for (int j = 0; j < M; j++) {
            cin >> S[j];
        }
        
        vector<long long> max_vals(M - K + 1);
        {
            deque<int> dq;
            for (int j = 0; j < M; j++) {
                while (!dq.empty() && S[dq.back()] <= S[j]) dq.pop_back();
                dq.push_back(j);
                if (dq.front() <= j - K) dq.pop_front();
                if (j >= K - 1) max_vals[j - K + 1] = S[dq.front()];
            }
        }
        
        vector<long long> min_vals(M - K + 1);
        {
            deque<int> dq;
            for (int j = 0; j < M; j++) {
                while (!dq.empty() && S[dq.back()] >= S[j]) dq.pop_back();
                dq.push_back(j);
                if (dq.front() <= j - K) dq.pop_front();
                if (j >= K - 1) min_vals[j - K + 1] = S[dq.front()];
            }
        }
        
        long long score = 0;
        for (int j = 0; j < M - K + 1; j++) {
            score = max(score, max_vals[j] - min_vals[j]);
        }
        
        if (score >= T) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。