概要

長さ \(N\) の数列から連続する \(K\) 要素を選び、それらをすべてその区間の平均値に置き換えたとき、操作後の数列全体の最大値としてあり得る最小の値を求める問題です。

考察

操作で選ぶ区間の左端のインデックスを \(i\) （0-indexed で \(0 \leq i \leq N-K\)）と固定して考えます。 区間 \([i, i+K-1]\) を選んで平均値に置き換えたとき、操作後の数列全体の最大値は、以下の 3 つの値の最大値になります。

1. 区間の左側（\(0\) から \(i-1\) 番目）の要素の最大値
2. 区間の右側（\(i+K\) から \(N-1\) 番目）の要素の最大値
3. 区間内の平均値

これをすべての \(i\) について愚直に計算すると、各 \(i\) に対して区間内の和や左右の最大値を求めるのに \(O(N)\) の時間がかかり、全体で \(O(N^2)\) となります。今回の制約は \(N \leq 10^6\) であるため、これでは実行時間制限（TLE）に間に合いません。

そこで、これら 3 つの値を各 \(i\) に対して \(O(1)\) で高速に取得できるように、前計算（累積和・累積最大値）を行います。

アルゴリズム

各 \(i\) に対する 3 つの値を高速に求めるために、以下の 3 つの配列を事前に構築します。

1. 累積和（Prefix Sum）

区間内の総和を \(O(1)\) で求めるために、配列 \(F\) の累積和 \(S\) を用意します。 \(S[x] = \sum_{j=0}^{x-1} F_j\) （ただし \(S[0] = 0\)）と定義すると、区間 \([i, i+K-1]\) の総和は \(S[i+K] - S[i]\) で求まります。 したがって、平均値は \(\displaystyle \text{avg} = \frac{S[i+K] - S[i]}{K}\) となります。

2. 左からの累積最大値（Prefix Max）

区間の左側の最大値を \(O(1)\) で求めるために、左からの累積最大値の配列 \(L\) を用意します。 \(L[i] = \max(F_0, F_1, \ldots, F_{i-1})\) と定義します。 これは \(L[i] = \max(L[i-1], F_{i-1})\) という関係式を用いて、左から順番に走査することで \(O(N)\) で構築できます。

3. 右からの累積最大値（Suffix Max）

区間の右側の最大値を \(O(1)\) で求めるために、右からの累積最大値の配列 \(R\) を用意します。 \(R[j] = \max(F_j, F_{j+1}, \ldots, F_{N-1})\) と定義します。 これも同様に、右から順番に走査することで \(O(N)\) で構築できます。

---

これらの前計算を行うことで、各 \(i\)（\(0 \leq i \leq N-K\)）における操作後の最大値は、 $\(\max(L[i], R[i+K], \text{avg})\)\( として \)O(1)\( で計算可能になります。この値の全 \)i$ における最小値が求める答えになります。

計算量

• 時間計算量: \(O(N)\) 累積和および左右からの累積最大値の構築に \(O(N)\) かかります。その後の各 \(i\) に対する最大値の判定は \(O(1)\) で行えるため、ループ全体でも \(O(N)\) となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\) 累積和配列 \(S\)、累積最大値配列 \(L, R\) を保持するために、それぞれサイズ \(O(N)\) の配列を使用します。

実装のポイント

• 境界値の処理 \(i = 0\) のときは「区間の左側」が存在せず、\(i = N-K\) のときは「区間の右側」が存在しません。存在しない部分の最大値が結果に影響を与えないよう、配列 \(L\) の先頭や配列 \(R\) の末尾には十分小さな値（\(-10^{18}\) など）を番兵として挿入しておきます。

• 浮動小数点数の演算 平均値の計算で毎回 \(K\) による除算を行う代わりに、あらかじめ inv_K = 1.0 / K を計算しておき、掛け算（(S[i+K] - S[i]) * inv_K）に変換することで、わずかですが実行時間を高速化することができます。

  ソースコード

import sys
from itertools import accumulate


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])

    F = list(map(int, input_data[2 : 2 + N]))

    INF = 10**18

    L = [-INF] + list(accumulate(F, max))
    R = list(accumulate(F[::-1], max))[::-1] + [-INF]
    S = [0] + list(accumulate(F))

    ans = INF
    inv_K = 1.0 / K

    for i in range(N - K + 1):
        l_max = L[i]
        r_max = R[i + K]
        avg = (S[i + K] - S[i]) * inv_K
        cur = l_max if l_max > r_max else r_max
        if avg > cur:
            cur = avg
        if cur < ans:
            ans = cur

    print(f"{ans:.12f}")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。