概要

街灯 \(T\) を消灯（明るさを \(0\) に置換）した上で、街灯 \(T\) を含む長さ \(K\) の連続区間すべてについて区間最小値（安全度）を求め、その最大値を出力する問題です。

考察

問題の整理

まず、配列 \(A\) を作ります。\(A_i = S_i\)（\(i \neq T\) のとき）、\(A_T = 0\) です。

次に、街灯 \(T\) を含む長さ \(K\) のウィンドウの開始位置 \(l\) の範囲を考えます。\(l\) は以下を満たす必要があります：

• \(1 \leq l\) かつ \(l + K - 1 \leq N\)（ウィンドウが通り全体に収まる）
• \(l \leq T \leq l + K - 1\)（ウィンドウが街灯 \(T\) を含む）

これを整理すると、\(l\) は \(\max(1,\, T - K + 1)\) から \(\min(N - K + 1,\, T)\) までの範囲です。

各 \(l\) に対して \(\min(A_l, A_{l+1}, \ldots, A_{l+K-1})\) を求め、その最大値を答えます。

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

各ウィンドウに対して愚直に最小値を求めると、ウィンドウの数は最大 \(K\) 個、各ウィンドウのサイズは \(K\) なので、最悪 \(O(K^2)\) かかります。\(K\) が最大 \(5 \times 10^5\) のため、これでは間に合いません。

解決策

スライディングウィンドウ最小値（deque を使ったテクニック）を用いれば、連続するウィンドウすべての最小値を \(O(N)\) で計算できます。

アルゴリズム

1. 配列 \(A\) を構築する（\(A[T] = 0\)、それ以外は \(S_i\) をそのまま使う）。
2. 有効なウィンドウ開始位置の範囲 \([l_{\min},\, l_{\max}]\) を計算する。
3. deque（両端キュー）を用いたスライディングウィンドウ最小値を実行する：
   • インデックス \(i\) を \(l_{\min}\) から \(l_{\max} + K - 1\) まで走査する。
   • deque の末尾から、\(A[\text{末尾}] \geq A[i]\) であるインデックスを除去し、\(i\) を追加する。
   • ウィンドウ開始位置 \(l_0 = i - K + 1\) が \(l_{\min}\) 以上になったら、deque の先頭からウィンドウ外のインデックスを除去し、\(A[\text{先頭}]\) がそのウィンドウの最小値となる。
4. 全ウィンドウの最小値のうち最大のものを出力する。

具体例

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

• \(A = [2, 5, 0, 1, 4]\)（\(A[3] = 0\)）
• 有効な \(l\)：\(l=1\) → 区間 \([2,5,0]\) → 最小 \(0\)、\(l=2\) → \([5,0,1]\) → 最小 \(0\)、\(l=3\) → \([0,1,4]\) → 最小 \(0\)
• 最大値は \(0\)

計算量

• 時間計算量: \(O(N)\) — 配列構築に \(O(N)\)、スライディングウィンドウ処理で各要素は deque に最大1回追加・1回削除されるため \(O(N)\)。
• 空間計算量: \(O(N)\) — 配列 \(A\) と deque の格納に必要。

実装のポイント

• 0-indexed と 1-indexed の変換：問題は 1-indexed ですが、配列操作は 0-indexed で行うため、\(T\) を 0-indexed に変換して処理しています。

• deque の単調性：deque には「値が単調増加」となるようにインデックスを保持します。これにより、deque の先頭が常にウィンドウ内の最小値を指します。

• ウィンドウ範囲の正確な計算：\(l_{\min} = \max(0,\, T\_idx - K + 1)\)、\(l_{\max} = \min(N - K,\, T\_idx)\) と正しく設定することが重要です。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    T = int(input_data[2])
    S = [int(input_data[3 + i]) for i in range(N)]
    
    # T is 1-indexed
    T_idx = T - 1  # 0-indexed
    
    # Build array A where A[T_idx] = 0, else A[i] = S[i]
    A = S[:]
    A[T_idx] = 0
    
    # We need all l (1-indexed) such that:
    # 1 <= l, l + K - 1 <= N, l <= T <= l + K - 1
    # In 0-indexed: l0 ranges, window [l0, l0+K-1]
    # l0 <= T_idx <= l0 + K - 1
    # l0 >= 0, l0 + K - 1 <= N - 1
    # So l0 ranges from max(0, T_idx - K + 1) to min(N - K, T_idx)
    
    l_min = max(0, T_idx - K + 1)
    l_max = min(N - K, T_idx)
    
    # We need to compute min of A[l0..l0+K-1] for each l0 in [l_min, l_max]
    # and find the maximum of these minimums.
    
    # Use sliding window minimum with a deque over the full range of windows
    # that could be relevant. The windows start from l_min to l_max.
    # All windows have size K.
    
    # Sliding window minimum approach:
    # We process elements from l_min to l_max + K - 1
    # and maintain a deque of indices with increasing A values.
    
    ans = -float('inf')
    dq = deque()  # stores indices, A[dq[0]] is the minimum in current window
    
    start = l_min
    end = l_max + K - 1  # last element index we need to consider
    
    for i in range(start, end + 1):
        # Remove elements from back that are >= A[i]
        while dq and A[dq[-1]] >= A[i]:
            dq.pop()
        dq.append(i)
        
        # The window for l0 = i - K + 1 is [i-K+1, i]
        l0 = i - K + 1
        if l0 >= l_min:
            # Remove elements outside the window from front
            while dq[0] < l0:
                dq.popleft()
            # Minimum of this window
            window_min = A[dq[0]]
            if window_min > ans:
                ans = window_min
    
    print(ans)

main()

---

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