概要

街灯の一つを消灯したとき、その街灯を含む長さ \(K\) の連続区間すべてにおいて、各区間の最小値（安全度）の最大値を求める問題です。

考察

この問題では、指定された位置 \(T\) の街灯の明るさを一時的に \(0\) にし、その街灯を含むすべての長さ \(K\) の区間について、区間内の最小値（安全度）を求め、その中の最大値を答えとする必要があります。

素朴な方法として、すべての有効な区間を列挙し、それぞれについて最小値を愚直に求めることも可能ですが、これは最大で \(O(NK)\) の計算量となり、制約 \(N \leq 5 \times 10^5\) ではTLE（時間超過）になります。

そこで、区間の最小値を高速に求められるアルゴリズムが必要になります。特に、区間がスライドする様子に注目すると、スライディングウィンドウ最小値を求める典型的な問題であることが分かります。これは、deque（両端キュー）を用いることで効率的に計算できます。

また、街灯 \(T\) を含まない区間については考える必要がないので、区間の開始位置 \(l\) は以下のように制限されます： - \(l \leq T\) - \(l + K - 1 \geq T\)

これを整理すると、\(l\) の範囲は
$\( \max(0, T - K + 1) \leq l \leq \min(N - K, T) \)$
となります。

アルゴリズム

1. 入力を読み込み、街灯 \(T\) の明るさを \(0\) に変更します（0-indexedに変換）。
2. 上記の条件に基づいて、考慮すべき区間の開始位置の範囲 \([l_{\min}, l_{\max}]\) を求めます。
3. deque を用いたスライディングウィンドウ最小値のテクニックを用いて、各区間の最小値を高速に求めます。
   • deque には、現在の区間内の要素のインデックスを、対応する値が単調増加になるように保持します。
   • 新しい要素を追加する際は、末尾から不要な要素を削除しながら追加します。
   • 区間から外れる要素があれば、先頭から削除します。
4. 各区間の最小値を記録しながら、その最大値を更新していきます。
5. 最終的な最大値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素は deque に高々1回追加され、1回削除されるため、全体で線形時間で処理可能です。
• 空間計算量: \(O(K)\)
  • deque には最大で \(K\) 個の要素が格納されるため。

実装のポイント

• 街灯の番号は1-indexedで与えられるが、内部処理では0-indexedに変換しておくと扱いやすい。

• deque にはインデックスを格納し、その値に基づいて比較を行う。

• 区間の開始位置の範囲を正確に計算することが重要。

• 区間のスライドごとに、deque の先頭要素が区間内にあるか確認し、必要に応じて取り除く。

  ソースコード

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().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にする
    S[T] = 0
    
    # 対象となる区間[l, l+K-1]でTを含むようなlの範囲を求める
    # l <= T かつ l + K - 1 >= T
    # よって max(0, T - K + 1) <= l <= min(N - K, T)
    l_min = max(0, T - K + 1)
    l_max = min(N - K, T)
    
    # 各区間[l, l+K-1]について最小値を求め、その最大値を求める
    # 区間の最小値を効率的に求めるためにdequeを使ったスライディングウィンドウを使う
    
    # 各区間について最小値を求める
    max_safe = float('-inf')
    
    # dequeを初期化して最初の区間[l_min, l_min+K-1]の最小値を求める
    dq = deque()
    # 最初の区間を処理
    for i in range(l_min, l_min + K):
        while dq and S[dq[-1]] >= S[i]:
            dq.pop()
        dq.append(i)
    
    # 最初の区間の最小値をチェック
    current_min = S[dq[0]]
    if current_min > max_safe:
        max_safe = current_min
    
    # スライドしていく
    for l in range(l_min + 1, l_max + 1):
        # 新しく追加される要素のインデックス
        right = l + K - 1
        
        # 古い要素の削除（範囲外になったら）
        if dq and dq[0] < l:
            dq.popleft()
        
        # 新しい要素の追加
        while dq and S[dq[-1]] >= S[right]:
            dq.pop()
        dq.append(right)
        
        # 現在の最小値を取得
        current_min = S[dq[0]]
        if current_min > max_safe:
            max_safe = current_min
            
    print(max_safe)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。