概要

連続する \(K\) 地点の気温をその平均値に置き換える操作を1回行い、操作後の全地点の気温の最大値を最小化する問題です。全ての操作候補を効率的に評価して最適な選択を求めます。

考察

操作後の最大値の構造

ある位置 \(l\) を選んでグループ \([l, l+K-1]\) に操作を適用したとき、操作後の全地点の最大値は次の2つの大きい方になります：

1. グループ内の値：グループ内の全地点が平均値 \(\frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}\) に置き換わるので、グループ内の最大値はこの平均値そのもの
2. グループ外の値：グループに含まれない地点の気温は変化しないので、それらの最大値

つまり、操作後の最大値は： $\(\max\left(\frac{\sum_{i=l}^{l+K-1} F_i}{K},\ \max_{i \notin [l, l+K-1]} F_i\right)\)$

効率的な計算

全ての \(l\)（\(N - K + 1\) 通り）について上記を計算し、最小のものを選べばよいです。

• グループの平均値：累積和を前計算すれば \(O(1)\) で計算可能
• グループ外の最大値：前方からの累積最大値（prefix max）と後方からの累積最大値（suffix max）を前計算すれば \(O(1)\) で計算可能

例えば \(N=5, K=3, F = [3, 1, 4, 1, 5]\) のとき： - \(l=0\): 平均 \(= (3+1+4)/3 = 8/3 \approx 2.67\)、グループ外の最大値 \(= \max(1, 5) = 5\)、全体最大 \(= 5\) - \(l=1\): 平均 \(= (1+4+1)/3 = 2\)、グループ外の最大値 \(= \max(3, 5) = 5\)、全体最大 \(= 5\) - \(l=2\): 平均 \(= (4+1+5)/3 = 10/3 \approx 3.33\)、グループ外の最大値 \(= \max(3, 1) = 3\)、全体最大 \(\approx 3.33\)

この場合 \(l=2\) が最適です。

アルゴリズム

1. 累積和の構築: \(\text{prefix}[i] = F_0 + F_1 + \cdots + F_{i-1}\) を計算する
2. 前方累積最大値の構築: \(\text{prefix\_max}[i] = \max(F_0, F_1, \ldots, F_{i-1})\) を計算する
3. 後方累積最大値の構築: \(\text{suffix\_max}[i] = \max(F_i, F_{i+1}, \ldots, F_{N-1})\) を計算する
4. 各 \(l\) について評価:
   • グループ平均 \(= (\text{prefix}[l+K] - \text{prefix}[l]) / K\)
   • グループ外最大値 \(= \max(\text{prefix\_max}[l],\ \text{suffix\_max}[l+K])\)
   • 操作後最大値 \(= \max(\text{グループ平均},\ \text{グループ外最大値})\)
5. 全ての \(l\) に対する操作後最大値の最小値を出力する

計算量

• 時間計算量: \(O(N)\)（前計算に \(O(N)\)、各候補の評価に \(O(1)\) × \(O(N-K+1)\) 通り）
• 空間計算量: \(O(N)\)（累積和、前方/後方累積最大値の配列）

実装のポイント

• prefix_max と suffix_max の境界: \(\text{prefix\_max}[0] = -\infty\)、\(\text{suffix\_max}[N] = -\infty\) として初期化する。これにより \(l=0\)（左側にグループ外がない）や \(l=N-K\)（右側にグループ外がない）のケースも統一的に処理できる。

• 浮動小数点の出力: 平均値の計算は整数の割り算なので Python では自然に浮動小数点数になる。出力は十分な桁数（例えば10桁）で表示する。

• 高速入力: \(N\) が最大 \(10^6\) と大きいため、sys.stdin.buffer.read() による一括読み込みを使用して入力を高速化している。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    F = [int(input_data[i + 2]) for i in range(N)]
    
    # We need to choose l (1-indexed) such that we replace F[l-1..l+K-2] with their average.
    # After replacement, the max over all positions should be minimized.
    
    # For a given choice of l (0-indexed: replacing F[l..l+K-1]):
    # - The group average is sum(F[l..l+K-1]) / K
    # - The max outside the group is max of F[i] for i not in [l, l+K-1]
    # - The overall max is max(group_average, max_outside)
    
    # We want to minimize over all valid l of max(avg(l), max_outside(l))
    
    # Precompute prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + F[i]
    
    # Precompute prefix max and suffix max for computing max outside [l, l+K-1]
    # prefix_max[i] = max of F[0..i-1], with prefix_max[0] = -inf
    # suffix_max[i] = max of F[i..N-1], with suffix_max[N] = -inf
    
    NEG_INF = float('-inf')
    
    prefix_max = [NEG_INF] * (N + 1)
    for i in range(N):
        prefix_max[i + 1] = max(prefix_max[i], F[i])
    
    suffix_max = [NEG_INF] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_max[i] = max(suffix_max[i + 1], F[i])
    
    best = float('inf')
    
    for l in range(N - K + 1):
        # Group is [l, l+K-1]
        group_sum = prefix[l + K] - prefix[l]
        avg = group_sum / K
        
        # Max outside the group
        max_outside = max(prefix_max[l], suffix_max[l + K])
        
        current_max = max(avg, max_outside)
        
        if current_max < best:
            best = current_max
    
    print(f"{best:.10f}")

solve()

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