概要

この問題は、各観測地点における \(M\) 日間の気温データから、長さ \(K\) の連続する区間（スライディングウィンドウ）の「最大値と最小値の差」を求め、その最大値（気温変動スコア）が閾値 \(T\) 以上となる観測地点の数を数え上げる問題です。

考察

素朴なアプローチとその限界

各観測地点について、長さ \(K\) の区間は \(M - K + 1\) 個存在します。 それぞれの区間について、最大値と最小値を愚直に求めると、1つの区間あたり \(O(K)\) の時間がかかります。 この場合、1つの観測地点あたりの計算量は \(O(M \times K)\) となり、全体での計算量は \(O(N \times M \times K)\) となります。

制約を見ると、 \(N \times M \leq 2 \times 10^6\)、 \(K \leq 10^5\) であるため、最悪の場合（例： \(N = 20, M = 10^5, K = 5 \times 10^4\) など）には全体の計算量が \(10^{11}\) を超えてしまい、実行時間制限に間に合いません（TLE）。

したがって、「スライディングウィンドウ内の最大値・最小値」を効率よく求める方法が必要になります。

効率的な解決策：スライディングウィンドウ最大値・最小値

区間を1つずつ右にずらしていくとき、区間内の最大値と最小値は、両端キュー（Deque）を用いることで、各ステップ \(O(1)\) （全体で \(O(M)\) ）で効率的に更新・取得することができます。 このアルゴリズムを用いることで、1つの観測地点あたりの処理を \(O(M)\) に抑えることができ、全体で \(O(N \times M)\) の計算量で解くことが可能になります。

---

アルゴリズム

Deque を用いたスライディングウィンドウの管理

最大値を求めるための Deque dq_max と、最小値を求めるための Deque dq_min を用意します。 これらには、気温データの「インデックス」を保持します。

1. 最大値の管理 (dq_max)

dq_max の中身は、常にインデックスに対応する値が降順（先頭が最大、末尾が最小）になるように維持します。

新しい要素 \(S[j]\) を追加する際、以下の操作を行います： - dq_max の末尾にある要素を指す値が \(S[j]\) 以下である限り、それらの要素を末尾から取り除きます（ \(S[j]\) より小さい過去の要素は、今後最大値になり得ないため）。 - \(j\) を dq_max の末尾に追加します。 - dq_max の先頭にあるインデックスが、現在のウィンドウの範囲外（ \(j - K\) 以下）になった場合、先頭から取り除きます。

この操作により、常に dq_max の先頭（head）にあるインデックスが、現在の区間 \([j - K + 1, j]\) における最大値のインデックスになります。

2. 最小値の管理 (dq_min)

同様に、dq_min の中身は常にインデックスに対応する値が昇順（先頭が最小、末尾が最大）になるように維持します。

新しい要素 \(S[j]\) を追加する際： - dq_min の末尾にある要素を指す値が \(S[j]\) 以上である限り、それらの要素を末尾から取り除きます。 - \(j\) を dq_min の末尾に追加します。 - dq_min の先頭にあるインデックスが範囲外（ \(j - K\) 以下）になった場合、先頭から取り除きます。

これにより、常に dq_min の先頭にあるインデックスが、現在の区間における最小値のインデックスになります。

3. 判定

各ステップ \(j \geq K - 1\)（最初の区間が完成した後）において、現在の区間の最大値と最小値の差 mx - mn を計算します。 この差が \(T\) 以上であれば、その観測地点の気温変動スコアは \(T\) 以上であることが確定します。

---

計算量

• 時間計算量: \(O(N \times M)\)
  • 各観測地点において、各要素は Deque に「高々1回追加され、高々1回削除される」ため、1つの観測地点あたりの処理は \(O(M)\) です。
  • これを \(N\) 箇所で行うため、全体の計算量は \(O(N \times M)\) となります。これは制約 \(N \times M \leq 2 \times 10^6\) に対して十分に高速です。
• 空間計算量: \(O(M)\)
  • 1つの観測地点の気温データおよび Deque を保持するために必要なメモリは \(O(M)\) です。これらは次の観測地点の処理時に再利用できるため、全体での空間計算量は \(O(M)\) に抑えられます。

---

実装のポイント

1. 配列による Deque の自作 C++の標準ライブラリである std::deque は便利ですが、メモリの割り当てオーバーヘッドにより動作がやや遅いことがあります。 今回の実装では、サイズ \(M\) の std::vector を用意し、インデックスを表す変数 head と tail を用いて Deque を自作（簡易的なリングバッファ、または単方向の配列利用）しています。これにより、定数倍が非常に高速化されます。

2. 途中で条件を満たした場合の早期スキップ ある観測地点の処理中に、一度でも「最大値と最小値の差が \(T\) 以上」になった場合、その観測地点のスコアが \(T\) 以上になることは確定します。 そのため、フラグ ok を true にし、それ以降の Deque の更新処理をスキップ（if (ok) continue;）しています。 ※ただし、次の観測地点のデータを正しく読み込むために、入力（cin >> S[j]）自体はスキップせずに最後まで読み込む必要があります。

3. 入出力の高速化 入力データ数が最大で \(2 \times 10^6\) 個と非常に多いため、ios_base::sync_with_stdio(false); cin.tie(NULL); を用いて C++ の標準入出力を高速化しています。

   ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    long long T;
    if (!(cin >> N >> M >> K >> T)) return 0;

    vector<long long> S(M);
    vector<int> dq_max(M);
    vector<int> dq_min(M);

    int ans = 0;

    for (int i = 0; i < N; ++i) {
        int head_max = 0, tail_max = 0;
        int head_min = 0, tail_min = 0;
        bool ok = false;

        for (int j = 0; j < M; ++j) {
            cin >> S[j];
            if (ok) continue;

            // max deque
            while (tail_max > head_max && S[dq_max[tail_max - 1]] <= S[j]) {
                tail_max--;
            }
            dq_max[tail_max++] = j;
            if (dq_max[head_max] <= j - K) {
                head_max++;
            }

            // min deque
            while (tail_min > head_min && S[dq_min[tail_min - 1]] >= S[j]) {
                tail_min--;
            }
            dq_min[tail_min++] = j;
            if (dq_min[head_min] <= j - K) {
                head_min++;
            }

            if (j >= K - 1) {
                long long mx = S[dq_max[head_max]];
                long long mn = S[dq_min[head_min]];
                if (mx - mn >= T) {
                    ok = true;
                }
            }
        }
        if (ok) {
            ans++;
        }
    }

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

---

この解説は gemini-3.5-flash-high によって生成されました。