概要

連続する \(K\) 日以上の期間で、最高気温の最大値と最小値の差が \(D\) 以下であるものの中から、最長の日数を求める問題です。尺取り法と単調デック（モノトニックデック）を組み合わせて効率的に解きます。

考察

素朴なアプローチ

すべての連続区間 \([l, r]\) を試し、それぞれについて最大値・最小値を求めると、区間の選び方が \(O(N^2)\) 通り、各区間の最大値・最小値の計算に \(O(N)\) かかるので、全体で \(O(N^3)\) となり、\(N = 5 \times 10^5\) では到底間に合いません。

重要な気づき

1. 区間を広げると差は大きくなる: ある区間 \([l, r]\) が安定（最大値 - 最小値 \(\leq D\)）であるとき、この区間を狭めても安定性は保たれます。逆に広げると差が大きくなる可能性があります。この単調性が尺取り法を適用できる根拠です。

2. 尺取り法（しゃくとり法）: 右端 \(r\) を1つずつ進め、安定条件を満たさなくなったら左端 \(l\) を進めて条件を回復する、という方法で全区間を効率的に調べられます。

3. 区間の最大値・最小値の高速管理: 尺取りで窓をスライドさせる際、区間の最大値・最小値を \(O(1)\) で取得する必要があります。これには単調デック（monotonic deque）が使えます。

具体例

例えば \(H = [3, 1, 4, 1, 5]\)、\(K = 2\)、\(D = 2\) のとき：

• \([l=0, r=0]\): \(\{3\}\) → 差 \(0 \leq 2\) ✓、長さ \(1 < K\)
• \([l=0, r=1]\): \(\{3,1\}\) → 差 \(2 \leq 2\) ✓、長さ \(2 \geq K\) → 答え候補 \(2\)
• \([l=0, r=2]\): \(\{3,1,4\}\) → 差 \(3 > 2\) ✗ → \(l\) を進める
• \([l=1, r=2]\): \(\{1,4\}\) → 差 \(3 > 2\) ✗ → \(l\) を進める
• \([l=2, r=2]\): \(\{4\}\) → 差 \(0 \leq 2\) ✓、長さ \(1 < K\)
• …このように進めていきます。

アルゴリズム

1. 最大値用デック（降順）: デックの先頭が常に現在の窓 \([l, r]\) 内の最大値のインデックスを保持します。新しい要素を追加する際、末尾から自分以下の要素を除去します。

2. 最小値用デック（昇順）: デックの先頭が常に現在の窓 \([l, r]\) 内の最小値のインデックスを保持します。新しい要素を追加する際、末尾から自分以上の要素を除去します。

3. 尺取り法の流れ:

   • \(r\) を \(0\) から \(N-1\) まで進める。
   • \(r\) を追加するたびに両デックを更新する。
   • 窓内の最大値 \(-\) 最小値が \(D\) を超える間、\(l\) を \(1\) ずつ進め、デックの先頭が窓外に出たら除去する。
   • 窓の長さ \(r - l + 1 \geq K\) なら答えの候補として更新する。

4. 最終的に候補が見つからなければ \(-1\) を出力する。

計算量

• 時間計算量: \(O(N)\) — 各要素はデックに最大1回追加・最大1回除去されるため、全体で線形です。
• 空間計算量: \(O(N)\) — デックと入力配列の分です。

実装のポイント

• デックには値ではなくインデックスを格納します。これにより、左端 \(l\) を進めたときにデック先頭が窓外かどうかを max_deque[0] < l で判定できます。

• while ループで \(l\) を進める際、最大値デックと最小値デックの両方の先頭を確認してから条件を再チェックする必要があります。

• 答えの初期値を \(-1\) にしておき、\(K\) 日以上の安定期間が一度も見つからなければそのまま \(-1\) が出力される仕組みです。

  ソースコード

from collections import deque
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    H = [int(input_data[3 + i]) for i in range(N)]
    
    # Two pointers with monotonic deques for max and min
    max_deque = deque()  # decreasing
    min_deque = deque()  # increasing
    
    ans = -1
    l = 0
    
    for r in range(N):
        # Maintain max deque (decreasing)
        while max_deque and H[max_deque[-1]] <= H[r]:
            max_deque.pop()
        max_deque.append(r)
        
        # Maintain min deque (increasing)
        while min_deque and H[min_deque[-1]] >= H[r]:
            min_deque.pop()
        min_deque.append(r)
        
        # Shrink window from left if not stable
        while H[max_deque[0]] - H[min_deque[0]] > D:
            l += 1
            if max_deque[0] < l:
                max_deque.popleft()
            if min_deque[0] < l:
                min_deque.popleft()
        
        # Current window is [l, r], length = r - l + 1
        length = r - l + 1
        if length >= K:
            if ans < length:
                ans = length
    
    print(ans)

main()

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