概要

街灯の列から連続する \(K\) 本の区間の最小値（安全度）を計算するが、特定の街灯 \(T\) のみ消灯（値 \(0\)）されている状況で、街灯 \(T\) を含むすべての区間における安全度の最大値を求める問題です。

考察

問題の本質は、街灯 \(T\) が \(0\) に固定された状態で、\(T\) を含むすべての長さ \(K\) の連続部分配列の最小値の中から最大値を求めることです。素朴なアプローチでは、\(T\) を含む各区間（\(l\) の数は最大 \(K\) 個）について毎回最小値を計算すると \(O(K^2)\) 時間かかり、\(K\) が最大 \(5 \times 10^5\) にもなるため時間制限に間に合いません。効率的に解くには、スライディングウィンドウ最小値（最小値の追跡）を両端キュー（deque）を用いて \(O(N)\) 時間で計算する手法が適しています。

アルゴリズム

1. 入力処理: 街灯の数 \(N\)、区間長 \(K\)、消灯する街灯 \(T\)（\(0\) インデックスに調整）、明るさの配列 \(S\) を読み取ります。\(S[T]\) を \(0\) に設定します。
2. 区間 \(l\) の範囲の特定: \(T\) を含む長さ \(K\) の区間は、\(l\) が \(\max(0, T - K + 1)\) から \(\min(n - K, T)\) までの範囲です。
3. スライディングウィンドウ最小値の計算:
   • 両端キュー（deque）を用いて、現在のウィンドウ内で最小値をもつインデックスを保持します。
   • 配列を左から右にスキャンし、各ステップで:
     • ウィンドウからはみ出たインデックスをキューから削除（左端）。
     • 現在の要素がキューの末尾の要素より小さい場合、末尾を削除（より小さい値が来たら古い値は不要）。
     • 現在のインデックスをキューに追加。
   • ウィンドウが完全に形成されたら（\(i \geq K-1\)）、キューの先頭が現在のウィンドウの最小値です。
4. 条件に合う最小値の記録: 現在のウィンドウが街灯 \(T\) を含む場合（\(l \leq T \leq i\)）のみ、その最小値を記録し、最大値を更新します。
5. 結果の出力: 得られた最大の安全度を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素はキューに一度追加され、最大一度削除されるため、全体で \(O(N)\) 時間です。
• 空間計算量: \(O(N)\)
  • 配列 \(S\) の格納に \(O(N)\)、デックのサイズも最大 \(O(N)\) です。

実装のポイント

• デックにはインデックスを格納し、配列の値で比較することで、ウィンドウ外の要素の削除と最小値の追跡を効率的に行います。

• \(T\) を含むウィンドウのみを考慮するため、\(l\)（ウィンドウの開始インデックス）が \(T\) を含むかどうかをチェックします。

• 元の配列 \(S\) を変更していますが、問題の条件上 \(T\) のみ \(0\) にすれば十分です（後で戻す必要はありません）。

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    T = int(data[2]) - 1  # 0-indexed
    S = list(map(int, data[3:3+n]))
    
    # 街灯Tを0に設定
    original_T = S[T]
    S[T] = 0
    
    # 条件を満たすlの範囲を計算
    left_bound = max(0, T - k + 1)
    right_bound = min(n - k, T) + 1
    
    # スライディングウィンドウ最小値（両端キューを使用）
    dq = deque()
    result = -10**18
    
    # 左から右にウィンドウを動かしながら最小値を追跡
    for i in range(n):
        # ウィンドウからはみ出た要素を削除
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 新しい要素がキュー内の要素より小さい場合、不要な要素を削除
        while dq and S[dq[-1]] >= S[i]:
            dq.pop()
        
        dq.append(i)
        
        # ウィンドウが完全に範囲内にある場合のみ最小値を計算
        if i >= k - 1:
            window_min = S[dq[0]]
            l = i - k + 1
            # 街灯Tを含むウィンドウのみを考慮
            if l <= T <= i:
                if window_min > result:
                    result = window_min
    
    # 元の値を戻す（必要ないが）
    S[T] = original_T
    
    print(result)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。