概要

連続する日数の区間のうち、最高気温と最低気温の差が \(K\) 以下となる最長の区間の長さを求める問題です。尺取り法と単調デック（Monotonic Deque）を組み合わせて効率的に解きます。

考察

問題の言い換え

配列 \(A\) の連続部分列で、\(\max - \min \leq K\) を満たす最長のものを求めます。

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

全ての区間 \([l, r]\) を試し、各区間で最大値・最小値を求める方法を考えます。 - 区間の選び方: \(O(N^2)\) 通り - 各区間での最大・最小の計算: \(O(N)\) - 合計: \(O(N^3)\)

\(N = 2 \times 10^5\) では到底間に合いません。

重要な気づき

1. 尺取り法が使える条件: 区間 \([l, r]\) が条件を満たすなら、それより短い区間 \([l', r']\)（\(l \leq l' \leq r' \leq r\)）も必ず条件を満たします。つまり、\(r\) を固定したとき、条件を満たす最小の \(l\) が存在し、\(r\) が増えると \(l\) も単調に増加します。

2. 区間の最大・最小を高速に管理: 尺取り法では区間の端を1つずつ動かします。この際、単調デックを使えば、区間の最大値・最小値を \(O(1)\)（ならし）で更新できます。

アルゴリズム

単調デック（Monotonic Deque）とは

• 最大値用デック: 値が単調減少になるように管理。先頭が常に最大値。
• 最小値用デック: 値が単調増加になるように管理。先頭が常に最小値。

処理の流れ

1. 右端 right を 0 から \(N-1\) まで順に進める
2. right を追加する際、単調性を保つようにデックを更新
3. 最大値 - 最小値 \(> K\) の間、左端 left を進める
4. left より前のインデックスをデックから削除
5. 区間の長さ right - left + 1 の最大値を記録

具体例

\(A = [3, 1, 4, 1, 5]\), \(K = 2\) の場合：

right	区間	max	min	差	条件	長さ
0	[3]	3	3	0	○	1
1	[3,1]	3	1	2	○	2
2	[3,1,4]	4	1	3	× → left=1 → [1,4]	2
3	[1,4,1]	4	1	3	× → left=2 → [4,1] → × → left=3 → [1]	1
4	[1,5]	5	1	4	× → left=4 → [5]	1

答え: 2

計算量

• 時間計算量: \(O(N)\)
  • 各要素はデックに最大1回追加され、最大1回削除される
  • left と right はそれぞれ単調増加で、合計 \(O(N)\) 回の移動
• 空間計算量: \(O(N)\)
  • 2つのデックがそれぞれ最大 \(N\) 個の要素を保持

実装のポイント

1. デックにはインデックスを格納: 値そのものではなくインデックスを入れることで、left より前の要素を削除する判定が可能になる

2. 単調デックの更新順序:

   • まず right の要素を追加（単調性を壊す要素を後ろから削除）
   • その後で条件チェック → left を進める → 範囲外の要素を前から削除

3. 空のデックへのアクセス防止: while の条件で max_deque and min_deque を確認してから先頭要素にアクセス

   ソースコード

from collections import deque

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 0:
        print(0)
        return
    
    # 尺取り法 + 単調dequeで区間の最大・最小を管理
    max_deque = deque()  # 最大値を管理（単調減少）
    min_deque = deque()  # 最小値を管理（単調増加）
    
    left = 0
    ans = 0
    
    for right in range(N):
        # max_dequeに追加（単調減少を維持）
        while max_deque and A[max_deque[-1]] <= A[right]:
            max_deque.pop()
        max_deque.append(right)
        
        # min_dequeに追加（単調増加を維持）
        while min_deque and A[min_deque[-1]] >= A[right]:
            min_deque.pop()
        min_deque.append(right)
        
        # 条件を満たさない間、leftを進める
        while max_deque and min_deque and A[max_deque[0]] - A[min_deque[0]] > K:
            left += 1
            # leftより前のインデックスをdequeから削除
            while max_deque and max_deque[0] < left:
                max_deque.popleft()
            while min_deque and min_deque[0] < left:
                min_deque.popleft()
        
        # 現在の区間の長さを更新
        ans = max(ans, right - left + 1)
    
    print(ans)

solve()

---

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