概要

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

考察

各観測地点の気温列 \(S_{i,1}, S_{i,2}, \ldots, S_{i,M}\) に対して、長さ \(K\) の連続区間は全部で \(M-K+1\) 個あります。

例えば、\(M=5, K=3\) のとき、見る区間は次の \(3\) つです。

• \(S_{i,1}, S_{i,2}, S_{i,3}\)
• \(S_{i,2}, S_{i,3}, S_{i,4}\)
• \(S_{i,3}, S_{i,4}, S_{i,5}\)

それぞれの区間について最大値と最小値を求め、その差が最大のものがその観測地点の「気温変動スコア」です。

素朴な方法

各区間ごとに最大値・最小値を調べると、1 区間あたり \(O(K)\) かかります。

観測地点ごとに区間数は \(O(M)\) 個あるため、1 地点あたり \(O(MK)\)、全体では \(O(NMK)\) となります。

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

重要な気づき

連続する長さ \(K\) の区間は、1 つ右にずれるだけです。

つまり、次の区間へ移るときに、

• 左端の要素が 1 つ消える
• 右端に新しい要素が 1 つ追加される

だけです。

このような「スライドする区間」の最大値・最小値は、両端キュー deque を使うことで効率よく管理できます。

アルゴリズム

各観測地点について、以下を行います。

• 区間内の最大値候補を管理する dqMax
• 区間内の最小値候補を管理する dqMin

を用意します。

最大値の管理

dqMax には、値が大きい順になるように要素を保持します。

新しい値 \(x\) を追加するとき、

• 後ろにある \(x\) 以下の値は、今後最大値になる可能性がない
• そのため削除する

という処理をします。

すると、dqMax の先頭が現在の区間の最大値になります。

最小値の管理

dqMin には、値が小さい順になるように要素を保持します。

新しい値 \(x\) を追加するとき、

• 後ろにある \(x\) 以上の値は、今後最小値になる可能性がない
• そのため削除する

という処理をします。

すると、dqMin の先頭が現在の区間の最小値になります。

区間外の要素の削除

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

\(left = j - K + 1\)

です。

deque の先頭にある要素の添字が \(left\) より小さい場合、その要素は現在の区間の外に出ているので削除します。

判定

\(j \geq K-1\) になったら、長さ \(K\) の区間が完成しています。

このとき、

\(diff = \text{現在の最大値} - \text{現在の最小値}\)

を計算し、\(diff \geq T\) ならその観測地点は条件を満たします。

その観測地点について 1 回でも条件を満たす区間があれば、答えに \(1\) を加えます。

計算量

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

各要素は deque に高々 1 回追加され、高々 1 回削除されます。

そのため、1 観測地点あたり \(O(M)\)、全体で \(O(NM)\) です。

また、deque に保持される要素数は最大でも区間長 \(K\) 程度なので、空間計算量は \(O(K)\) です。

実装のポイント

• 最大値用の deque と最小値用の deque を別々に用意します。

• deque には値だけでなく、区間外になったか判定するために添字も一緒に保存します。

• 気温や差は最大で \(10^9\) や \(2 \times 10^9\) 程度になるため、long long を使うと安全です。

• \(T=0\) の場合、最大値と最小値の差は常に \(0\) 以上なので、すべての観測地点が条件を満たします。そのため、すぐに \(N\) を出力できます。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    long long T;
    cin >> N >> M >> K >> T;

    if (T == 0) {
        cout << N << '\n';
        return 0;
    }

    int ans = 0;

    for (int i = 0; i < N; i++) {
        deque<pair<int, long long>> dqMax, dqMin;
        bool ok = false;

        for (int j = 0; j < M; j++) {
            long long x;
            cin >> x;

            while (!dqMax.empty() && dqMax.back().second <= x) dqMax.pop_back();
            dqMax.emplace_back(j, x);

            while (!dqMin.empty() && dqMin.back().second >= x) dqMin.pop_back();
            dqMin.emplace_back(j, x);

            int left = j - K + 1;
            while (!dqMax.empty() && dqMax.front().first < left) dqMax.pop_front();
            while (!dqMin.empty() && dqMin.front().first < left) dqMin.pop_front();

            if (j >= K - 1) {
                long long diff = dqMax.front().second - dqMin.front().second;
                if (diff >= T) ok = true;
            }
        }

        if (ok) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

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