概要

街灯 \(T\) を一時的に \(0\) にしたうえで、「\(T\) を含む長さ \(K\) の全区間」それぞれの最小値（安全度）を求め、その最大値を出す問題です。

考察

まず、消灯中は街灯 \(T\) の値が必ず \(0\) になるので、配列を \(S_T \leftarrow 0\) と置き換えてしまって構いません。すると各区間の安全度は単に「その区間の最小値」になります。

次に、「\(T\) を含む長さ \(K\) の区間」は左端 \(l\) の範囲で表せます。区間は \([l, l+K-1]\) なので、 - そもそも長さ \(K\) の区間である条件：\(0 \le l \le N-K\) - \(T\)（0-indexで \(t\)）を含む条件：\(l \le t \le l+K-1\)

より、左端 \(l\) の許される範囲は $\( \max(0, t-K+1) \le l \le \min(t, N-K) \)$ となります（コードでは 0-indexで扱っています）。

素朴にやると、各 \(l\) ごとに区間の最小値を \(K\) 個見て求めるため \(O(K)\)、それを最大 \(O(N)\) 区間ぶん繰り返して最悪 \(O(NK)\) となり、\(N \le 5\times 10^5\) では到底間に合いません。

そこで「スライディングウィンドウ最小値」を使い、全ての長さ \(K\) の区間最小値を \(O(N)\) で列挙し、そのうち \(T\) を含む区間だけを拾って最大を取ります。

アルゴリズム

1. 入力を受け取り、0-index に直した \(t=T-1\) に対して \(S[t]=0\) に書き換える。
2. \(T\) を含む区間の左端の範囲を
   • \(l_{\min}=\max(0, t-K+1)\)
   • \(l_{\max}=\min(t, N-K)\) として求める。
3. deque（両端キュー）を使って、長さ \(K\) のスライディングウィンドウ最小値を求める。
   • deque には「値が単調増加になるように」インデックスを保持する。
   • 新しい要素 \(S[i]\) を入れるとき、末尾から \(S[\text{末尾}] \ge S[i]\) となるものを削除し、\(i\) を追加する。
   • ウィンドウから外れたインデックス（\(i-K\) 以下）を先頭から削除する。
   • こうすると、deque の先頭が常に現在のウィンドウの最小値の位置になる。
4. 各 \(i\) でウィンドウが完成する（\(i \ge K-1\)）たびに、そのウィンドウの左端 \(l=i-K+1\) を計算し、\(l_{\min} \le l \le l_{\max}\) を満たすときだけ最小値 \(S[\text{deque先頭}]\) で答え（最大値）を更新する。
5. 最終的な最大値を出力する。

具体例として、各長さ \(K\) の区間最小値を左から順に並べた配列を考えると、その中の「左端が \(l_{\min}\) から \(l_{\max}\) のもの」だけが \(T\) を含む区間なので、その部分の最大値を取っているイメージです。

計算量

• 時間計算量: \(O(N)\)（各要素は deque に高々1回入って高々1回出る）
• 空間計算量: \(O(K)\)（deque に入るのは最大でウィンドウ幅ぶん）

実装のポイント

• 0-index に直して考えると、左端範囲の式や deque の「範囲外判定」が書きやすいです。

• deque の単調性は「末尾の値が新しい値以上なら削除（\(>= \)）」としておくと、同値のときも新しい方を残し、範囲外削除と相性が良いです。

• 「\(T\) を含む区間だけ」を後から判定するために、全ウィンドウ最小値を求めながら、左端 \(l\) が範囲内のときだけ答えを更新しています。これで余計な前処理が要りません。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K, T = map(int, input().split())
    S = list(map(int, input().split()))
    t0 = T - 1
    S[t0] = 0

    l_low = max(0, t0 - K + 1)
    l_high = min(t0, N - K)

    dq = deque()
    ans = -10**30

    for i, x in enumerate(S):
        while dq and S[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - K:
            dq.popleft()

        if i >= K - 1:
            l = i - K + 1
            if l_low <= l <= l_high:
                ans = max(ans, S[dq[0]])

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。