概要

\(N\) 個のセンサーの温度データ \(A_i\) から、各センサーとその隣接するセンサーの合計値である「局所温度指標」を計算し、その中での最大値を求める問題です。

考察

各センサーの局所温度指標 \(M_i\) は、そのセンサーの位置によって計算式が異なります。

• 左端 (\(i=1\)): 自分と右隣の合計 (\(A_1 + A_2\))
• 右端 (\(i=N\)): 自分と左隣の合計 (\(A_{N-1} + A_N\))
• それ以外 (\(1 < i < N\)): 自分と両隣の合計 (\(A_{i-1} + A_i + A_{i+1}\))

\(N\) の値は最大で \(2 \times 10^5\) であるため、すべてのセンサーについて順番に計算を行っても、計算回数は \(N\) に比例する程度で済みます。したがって、1重のループを用いてすべての \(M_i\) を確認する素朴なアプローチで十分に制限時間内に正解を導き出すことができます。

注意点として、温度 \(A_i\) は負の値をとることもあるため、最大値を保持する変数の初期化には注意が必要です（最初の計算結果で初期化するのが安全です）。

アルゴリズム

以下の手順で実装します。

1. 入力された \(N\) 個のデータを配列 \(A\) に格納します。
2. まず、端のケースである \(M_1 = A_1 + A_2\) と \(M_N = A_{N-1} + A_N\) を計算し、その大きい方を暫定の最大値 ans とします。
3. 次に、ループ（for文）を用いて \(i = 2\) から \(N-1\) までのセンサーについて \(M_i = A_{i-1} + A_i + A_{i+1}\) を計算します。
4. 計算した \(M_i\) が現在の ans よりも大きければ、ans をその値で更新します。
5. 最終的な ans を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を 1 回ずつ走査するため、センサーの数に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の温度データを配列に保持するためのメモリが必要です。

実装のポイント

• 0-indexed への変換: プログラミング言語（Pythonなど）の配列は添字が 0 から始まるため、問題文の \(i\) 番目を配列の a[i-1] に対応させる必要があります。

  • \(M_1\) は a[0] + a[1]
  • \(M_N\) は a[n-2] + a[n-1]
  • \(M_i\) (\(1 < i < N\)) は a[i-2] + a[i-1] + a[i] となります。

• 効率的な入力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

  ソースコード

import sys

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    a = list(map(int, data[1:]))
    
    if n < 2:
        return
    
    m1 = a[0] + a[1]
    mn = a[n-2] + a[n-1]
    ans = m1 if m1 > mn else mn
    
    for i in range(1, n - 1):
        val = a[i-1] + a[i] + a[i+1]
        if val > ans:
            ans = val
            
    print(ans)

if __name__ == '__main__':
    solve()

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