概要

一列に並んだ温度センサーについて、各センサーの「自身と隣接センサーの計測値の合計」を計算し、その最大値を求める問題です。

考察

問題の理解

まず、局所温度指標の計算方法を整理しましょう： - 端のセンサー（\(i = 1\) や \(i = N\)）：隣が1つしかないので、自身 + 隣の1つ = 2つの合計 - 中間のセンサー（\(1 < i < N\)）：両隣があるので、左隣 + 自身 + 右隣 = 3つの合計

具体例で確認

例えば \(N = 5\)、\(A = [3, 1, 4, 1, 5]\) の場合： - \(M_1 = A_1 + A_2 = 3 + 1 = 4\) - \(M_2 = A_1 + A_2 + A_3 = 3 + 1 + 4 = 8\) - \(M_3 = A_2 + A_3 + A_4 = 1 + 4 + 1 = 6\) - \(M_4 = A_3 + A_4 + A_5 = 4 + 1 + 5 = 10\) - \(M_5 = A_4 + A_5 = 1 + 5 = 6\)

したがって、最大値は \(10\) です。

アプローチの検討

この問題は単純に各センサーについて局所温度指標を計算し、最大値を求めれば良いです。

• 素朴なアプローチ：各センサーについて定義通りに計算 → \(O(N)\)
• これは十分高速なので、そのまま実装すればACできます。

特別な最適化やアルゴリズムは不要で、制約 \(N \leq 2 \times 10^5\) に対して \(O(N)\) で十分間に合います。

アルゴリズム

1. センサーの個数 \(N\) と計測値の配列 \(A\) を読み込む
2. 最大値を保持する変数 max_m を十分小さい値（負の無限大）で初期化
3. \(i = 0\) から \(N-1\) まで順に以下を行う：
   • \(i = 0\)（先頭）の場合：\(M_i = A_0 + A_1\)
   • \(i = N-1\)（末尾）の場合：\(M_i = A_{N-2} + A_{N-1}\)
   • それ以外の場合：\(M_i = A_{i-1} + A_i + A_{i+1}\)
   • max_m を更新：max_m = max(max_m, M_i)
4. max_m を出力

計算量

• 時間計算量: \(O(N)\)
  • 各センサーについて定数時間で局所温度指標を計算
  • ループは \(N\) 回
• 空間計算量: \(O(N)\)
  • 入力の配列 \(A\) を保持するため

実装のポイント

1. 配列のインデックスに注意：問題文ではセンサー番号が \(1\) から始まりますが、Pythonでは配列のインデックスは \(0\) から始まります。コード中では \(0\)-indexed で処理しています。

2. 初期値の設定：計測値 \(A_i\) が負の値を取りうる（\(-10^9\) まで）ため、最大値の初期値は float('-inf')（負の無限大）にしています。\(0\) で初期化すると、すべての局所温度指標が負の場合に正しい答えが得られません。

3. オーバーフローの確認：局所温度指標は最大で3つの値の合計なので、最大 \(3 \times 10^9\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数型を使う必要があるかもしれません。

   ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    max_m = float('-inf')
    
    for i in range(N):
        if i == 0:
            m = A[0] + A[1]
        elif i == N - 1:
            m = A[N - 2] + A[N - 1]
        else:
            m = A[i - 1] + A[i] + A[i + 1]
        
        max_m = max(max_m, m)
    
    print(max_m)

solve()

---

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