概要

\(N\) 個の観測地点のそれぞれについて、過去 \(M\) 日間の連続する \(K\) 日間の区間内での「最大値と最小値の差」の最大値を求め、その値が閾値 \(T\) 以上である観測地点の個数を数える問題です。

考察

• 素朴なアプローチとその課題: すべての長さ \(K\) の区間について、最大値と最小値を一から探す方法がまず思いつきます。しかし、1つの区間の最大・最小を求めるのに \(O(K)\) 時間かかり、1つの観測地点で \(M-K+1\) 個の区間を調べるため \(O(M \times K)\) 時間かかってしまいます。\(N \times M\) が \(2 \times 10^6\) で \(K\) も \(10^5\) 程度になり得るため、全体で \(O(N \times M \times K)\) となり TLE（時間制限超過）してしまいます。
• 解決策: 「連続する区間を右へずらしていく」という操作に注目します。1つ右の区間へ移動するとき、左端の1個が消え、右端の1個が加わるだけです。この区間の更新を効率的に行えるデータ構造「両端キュー（Deque）」を使えば、各区間の最大値と最小値を \(O(1)\) で知ることができ、1つの観測地点あたり \(O(M)\) で計算可能になります。

アルゴリズム

「スライディングウィンドウ最大値・最小値」という手法を使います。 - 配列を左から右へ1つずつ要素を追加していきます。 - 最大値を求めるためのキューと最小値を求めるためのキューの2つを用意します。 - 最大値キューの更新ルール: 新しい要素を追加するとき、既にキューに入っている要素のうち、新しい要素以下のものは今後「最大値」になることは絶対にないため、キューから追い出します（後ろから順に確認）。これにより、キューの中は「降順（大きい順）」に保たれます。 - 最小値キューの更新ルール: 同樣に、新しい要素以上のものは「最小値」になることはないので、キューから追い出します。キューの中は「昇順（小さい順）」に保たれます。 - 古い要素の削除: ウィンドウの長さが \(K\) を超えたら、左端から \(K\) 個以上前に入った要素をキューから追い出します（前から確認）。 - スコアの計算: ウィンドウの長さが \(K\) に達したとき、最大値キューの一番前が「その区間の最大値」、最小値キューの一番前が「その区間の最小値」です。その差を計算し、その観測地点での最大値を更新していきます。 - 全ての区間を調べた後、最大スコアが \(T\) 以上なら答を \(1\) つ増やします。

計算量

• 時間計算量: \(O(N \times M)\) 各要素がキューに追加・削除される回数は高々1回ずつであるため、1つの観測地点の処理は \(O(M)\) で終わります。
• 空間計算量: \(O(N \times M)\) 入力データを保持するための領域と、スライディングウィンドウ用のキュー（長さ \(M\) の配列）を用意するため \(O(N \times M + M)\) となりますが、これは \(O(N \times M)\) に含まれます。

実装のポイント

• Pythonにおいて collections.deque を使う方法もありますが、高速化を図るため、自前で配列（リスト）と2つのポインタ（左端 l、右端 r）を用意してデックをシミュレートすると定数倍が小さくなります。

• \(K = 1\) の場合、区間内の最大値と最小値が同じになるため、常にスコアは \(0\) になります。そのため \(T \leq 0\) のときのみ条件を満たします。これを明示的に処理するとロジックがシンプルになります。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    T = int(data[3])
    
    ans = 0
    
    max_dq_buf = [0] * M
    min_dq_buf = [0] * M
    
    idx = 4
    for _ in range(N):
        A = [int(x) for x in data[idx:idx+M]]
        idx += M
        
        if K == 1:
            if 0 >= T:
                ans += 1
            continue
            
        max_score = -1
        
        max_l = 0
        max_r = 0
        min_l = 0
        min_r = 0
        
        for i in range(M):
            val = A[i]
            
            while max_r > max_l and A[max_dq_buf[max_r - 1]] <= val:
                max_r -= 1
            max_dq_buf[max_r] = i
            max_r += 1
            
            while min_r > min_l and A[min_dq_buf[min_r - 1]] >= val:
                min_r -= 1
            min_dq_buf[min_r] = i
            min_r += 1
            
            if max_dq_buf[max_l] <= i - K:
                max_l += 1
            if min_dq_buf[min_l] <= i - K:
                min_l += 1
                
            if i >= K - 1:
                diff = A[max_dq_buf[max_l]] - A[min_dq_buf[min_l]]
                if diff > max_score:
                    max_score = diff
                    
        if max_score >= T:
            ans += 1
            
    print(ans)

solve()

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