概要

長さ \(K\) の連続区間を 1 つ選び、その区間を平均値で一斉に置き換えた後の「最大気温」を最小化する問題です。全ての選び方 \(l\) について操作後の最大値を高速に求め、最小を取ります。

考察

操作で変わるのは選んだ区間 \([l,\,l+K-1]\) のみで、そこは全て同じ値（平均）になります。よって操作後の最大値は

• 区間内：平均値 \(\displaystyle \text{avg}(l)=\frac{F_l+\cdots+F_{l+K-1}}{K}\)
• 区間外：元の値のままなので、区間外の最大値

の大きい方です。つまり [ \max_i F’i \;=\; \max\Bigl(\text{avg}(l),\;\max{i \notin [l,l+K-1]} F_i\Bigr) ] となります。

素朴な方法がダメな理由

各 \(l\) について - 区間和を毎回 \(O(K)\) で計算し、 - さらに区間外の最大を毎回 \(O(N)\) で探す

のようにやると、最悪で \(O(N^2)\) になり、\(N\le 10^6\) では確実に TLE です。

どう解決するか

• 区間の平均：スライディングウィンドウで区間和を更新すれば、各 \(l\) あたり \(O(1)\)
• 区間外の最大：前計算で「左側の最大」「右側の最大」を作れば、各 \(l\) あたり \(O(1)\)

これで全体 \(O(N)\) にできます。

アルゴリズム

1. 配列 \(F\) を読む。同時に最初の区間（\(l=1\)）の和 \(ws=F_1+\cdots+F_K\) を作る。
2. prefix 最大を作る：
   [ \text{pre}[i] = \max(F_1,\dots,F_i)\quad (i=1..N),\;\text{pre}[0]=- \infty ] これで「区間の左側（\(1..l-1\)）の最大」は \(\text{pre}[l-1]\) で取れます（コードでは 0-index の都合で \(\text{pre}[l]\) を使用）。
3. suffix 最大を作る：
   [ \text{suf}[i] = \max(F_i,\dots,F_N)\quad (i=1..N),\;\text{suf}[N+1]=-\infty ] これで「区間の右側（\(l+K..N\)）の最大」は \(\text{suf}[l+K]\) で取れます（コードは 0-index）。
4. 各 \(l\)（0-index で \(l=0..N-K\)）について：
   • 平均 \(\text{avg} = ws / K\)
   • 区間外最大 \(m_{\text{out}} = \max(\text{pre}[l],\;\text{suf}[l+K])\)
   • 操作後の最大値は \(\max(\text{avg},\;m_{\text{out}})\)
   • その最小値を更新
   • 次の \(l\) のためにスライディング更新：
     [ ws \leftarrow ws + F_{l+K} - F_l ]
5. 求めた最小値を実数として出力する。

具体例（考え方）

\(F=[1,10,2,8,4],\;K=3\) とすると、 - \(l=1\) の区間は \([1,10,2]\)、平均は \(13/3\approx4.33\)、区間外は \([8,4]\) で最大 \(8\)
→ 操作後最大は \(\max(4.33,8)=8\) - \(l=2\) の区間は \([10,2,8]\)、平均は \(20/3\approx6.67\)、区間外は \([1,4]\) で最大 \(4\)
→ 操作後最大は \(\max(6.67,4)=6.67\)

このように「平均」と「区間外最大」の最大を比較するだけで評価できます。

計算量

• 時間計算量: \(O(N)\)（prefix/suffix 作成が \(O(N)\)、全ての \(l\) の走査も \(O(N)\)）
• 空間計算量: \(O(N)\)（\(F\), prefix, suffix を保持）

実装のポイント

• 区間外最大の取り方：区間が \([l,\,l+K-1]\) のとき、外側は「左：\([0,l-1]\)」「右：\([l+K,N-1]\)」。それぞれを prefix/suffix から \(O(1)\) で取ります。

• 平均は実数なので ws / float(K) として計算します（切り捨て不要）。

• \(N=10^6\) と大きいので、Python では 高速入力（sys.stdin.buffer.read()）や array('q')（64bit 整数）を使うと安定します。

  ソースコード

import sys
from array import array

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        sign = 1
        if data[idx] == 45:  # '-'
            sign = -1
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return sign * num

    N = next_int()
    K = next_int()

    F = array('q')
    appendF = F.append

    ws = 0
    for i in range(N):
        x = next_int()
        appendF(x)
        if i < K:
            ws += x

    NEG_INF = -(1 << 60)

    pre = array('q')
    pre_append = pre.append
    pre_append(NEG_INF)
    m = NEG_INF
    for x in F:
        if x > m:
            m = x
        pre_append(m)

    suf = array('q', [NEG_INF]) * (N + 1)
    m = NEG_INF
    for i in range(N - 1, -1, -1):
        x = F[i]
        if x > m:
            m = x
        suf[i] = m
    suf[N] = NEG_INF

    best = float('inf')
    Kf = float(K)
    NK = N - K

    for l in range(NK + 1):
        avg = ws / Kf
        mout = pre[l]
        rmax = suf[l + K]
        if rmax > mout:
            mout = rmax
        val = float(mout) if mout > avg else avg
        if val < best:
            best = val
        if l < NK:
            ws += F[l + K] - F[l]

    sys.stdout.write(f"{best:.10f}\n")

if __name__ == "__main__":
    main()

---

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