概要

この問題は、長さ \(N\) の配列から長さ \(K\) の連続する区間を \(1\) つ選び、その区間内の要素をすべて「区間内の平均値」に置き換えたときに、配列全体の最大値を最小化する問題です。

適切な前処理（累積和と左右からの累積最大値）を行うことで、各区間を選んだ場合の最大値を \(O(1)\) で計算できるようになり、全体として \(O(N)\) の時間計算量で解くことができます。

---

考察

1. 操作後の最大値がどうなるかを考える

ある区間 \([l, l+K-1]\) を選んで平滑化操作を行ったとき、操作後の配列の要素は以下の 2 つのグループに分かれます。

1. 区間内の要素: すべて平均値 \(\text{avg} = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}\) に置き換わります。
2. 区間外の要素: 元の気温 \(F_i\) のまま変化しません。

したがって、操作後の全体の最大値は、「区間外の要素の最大値」と「区間内の平均値」の大きい方になります。 $\(\text{操作後の最大値} = \max(\text{区間外の最大値}, \text{区間内の平均値})\)$

選べる区間の左端 \(l\) は \(1 \le l \le N-K+1\) の範囲を動くため、すべての \(l\) について上記の「操作後の最大値」を計算し、その中の最小値を求めればよいことになります。

2. 素朴なアプローチとその限界

各 \(l\) に対して、愚直に区間外の最大値や区間内の平均値を計算すると、1 回の計算に \(O(N)\) の時間がかかってしまいます。 \(l\) の候補数は \(O(N)\) 個あるため、全体の計算量は \(O(N^2)\) となり、制約の \(N \le 10^6\) では実行時間制限（TLE）になってしまいます。

これを解決するために、「区間内の平均値」と「区間外の最大値」をそれぞれ \(O(1)\) で高速に取得する工夫（前処理）が必要になります。

---

アルゴリズム

① 累積和による平均値の高速化

区間 \([l, l+K-1]\) の総和を高速に求めるために、累積和を利用します。 \(Sum[i] = F_1 + F_2 + \cdots + F_i\) （ただし \(Sum[0] = 0\)）となる配列 \(Sum\) をあらかじめ用意しておくと、区間の総和は以下のように \(O(1)\) で計算できます。 $\(\text{区間の総和} = Sum[l+K-1] - Sum[l-1]\)\( これを \)K\( で割ることで、平均値 \)\text{avg}\( も \)O(1)$ で求まります。

② 左右からの累積最大値による区間外最大値の高速化

区間外は、選んだ区間の「左側 \([1, l-1]\)」と「右側 \([l+K, N]\)」の 2 つに分かれます。 それぞれの区間における最大値を高速に求めるため、以下の 2 つの配列をあらかじめ構築しておきます。

• プレフィックス最大値 \(P\): 左端からの最大値 \(P[i] = \max(F_1, F_2, \ldots, F_i)\)
• サフィックス最大値 \(S\): 右端からの最大値 \(S[i] = \max(F_i, F_{i+1}, \ldots, F_N)\)

これらを用意しておくことで、区間外の最大値は以下のように \(O(1)\) で求まります。 $\(\text{区間外の最大値} = \max(P[l-1], S[l+K])\)$

③ 全体の流れ

1. 累積和配列 \(Sum\)、プレフィックス最大値配列 \(P\)、サフィックス最大値配列 \(S\) をそれぞれ \(O(N)\) で構築します。
2. \(l = 1, 2, \ldots, N-K+1\) について、以下を計算します。
   • \(\text{max\_outside} = \max(P[l-1], S[l+K])\)
   • \(\text{avg} = \frac{Sum[l+K-1] - Sum[l-1]}{K}\)
   • \(\text{current\_max} = \max(\text{max\_outside}, \text{avg})\)
3. すべての \(l\) における \(\text{current\_max}\) の最小値を出力します。

---

計算量

• 時間計算量: \(O(N)\) 前処理（累積和、左右からの最大値の構築）に \(O(N)\) かかります。その後の \(l\) に関するループは \(N-K+1\) 回まわり、各ループ内は \(O(1)\) で処理できるため、全体の時間計算量は \(O(N)\) となり、十分に高速です。

• 空間計算量: \(O(N)\) 入力の保存、および前処理用の配列（\(Sum, P, S\)）にそれぞれ長さ \(O(N)\) の配列を使用するため、空間計算量は \(O(N)\) となります。

---

実装のポイント

• 境界値（端の処理）への配慮: \(l=1\) のときは左側の区間 \([1, l-1]\) が空になり、\(l=N-K+1\) のときは右側の区間 \([l+K, N]\) が空になります。 このような「存在しない区間」の最大値を求める処理をシンプルにするため、コード中では \(P[0]\) や \(S[N+1]\) に十分に小さい値（\(-2 \times 10^{18}\) など、気温 \(F_i\) の最小値よりも遥かに小さい値）をあらかじめ格納しています。これにより、条件分岐（if 文）を書くことなくスマートに例外処理を行えます。

• 型と精度: 気温の総和は最大で \(10^6 \times 10^9 = 10^{15}\) に達するため、オーバーフローを防ぐために long long 型（64bit整数型）を使用します。また、平均値の計算や最小値の保持には、十分な精度を持つ浮動小数点数（double型など）を使用し、出力時には小数点以下の桁数を多めに指定します。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> F(N);
    for (int i = 0; i < N; ++i) {
        cin >> F[i];
    }

    // P[i]: F[0] から F[i-1] までの最大値
    vector<long long> P(N + 1);
    P[0] = -2e18; 
    for (int i = 0; i < N; ++i) {
        P[i + 1] = max(P[i], F[i]);
    }

    // S[i]: F[i-1] から F[N-1] までの最大値
    vector<long long> S(N + 2);
    S[N + 1] = -2e18;
    for (int i = N - 1; i >= 0; --i) {
        S[i + 1] = max(S[i + 2], F[i]);
    }

    // 累積和
    vector<long long> Sum(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        Sum[i + 1] = Sum[i] + F[i];
    }

    double min_max_val = 1e18; 

    for (int l = 1; l <= N - K + 1; ++l) {
        long long max_outside = max(P[l - 1], S[l + K]);
        double avg = (double)(Sum[l + K - 1] - Sum[l - 1]) / K;
        double current_max = max((double)max_outside, avg);
        if (current_max < min_max_val) {
            min_max_val = current_max;
        }
    }

    cout << fixed << setprecision(12) << min_max_val << "\n";

    return 0;
}

---

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