概要

各チェックポイントに景観スコアと移動コストが設定された山道において、途中でハイキングを終了できるときに得られる「満足度」の最大値を求めます。

考察

この問題では、チェックポイント \(1\) から \(k\) 番目までの スコアの合計 から、チェックポイント \(1\) から \(k\) に至るまでの 移動コストの合計 を引いた値（満足度）を最大化するような終了地点 \(k\) を選びたいです。

満足度は次のように定義されます： $\( \text{満足度}(k) = \left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right) \)$

素朴な方法として、全ての \(k\) に対して上記の和を毎回計算すると、時間計算量が \(O(N^2)\) になってしまい、制約 \(N \leq 10^6\) では間に合いません（TLE）。

しかし、満足度の式をよく見ると、累積和を使って効率的に求められることに気づけます。つまり、前から順番に走査しながら、現在の位置までのスコアの合計とコストの合計を保持しておけば、毎回和を計算し直さなくても済みます。

また、\(k = 1\) のときは移動が発生しないので、満足度は単に \(S_1\) になります。

したがって、累積和の考え方を用いることで、時間計算量 \(O(N)\) で解くことが可能です。

アルゴリズム

1. 最初に、\(k = 1\) のときの満足度 \(S_1\) を最大値の初期値とする。
2. スコアの累積和 \(current\_sum\_S\) とコストの累積和 \(current\_sum\_C\) を管理する変数を用意し、最初はそれぞれ \(S_1\) と \(0\) で初期化。
3. \(k = 2\) から \(N\) までループを回し、以下を行う：
   • \(current\_sum\_S\) に \(S_k\) を加える。
   • \(current\_sum\_C\) に \(C_{k-1}\) を加える。
   • 現在の満足度 \(current\_sum\_S - current\_sum\_C\) を計算。
   • それがこれまでの最大値より大きければ更新。
4. 最後に最大値を出力。

このようにすることで、すべての終了地点についての満足度を高速に計算でき、その最大値を求めることができます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を除く）

実装のポイント

• 累積和を変数で持ちながら逐次更新することで、毎回和を計算し直さない。

• 1-indexed と 0-indexed のインデックスの扱いに注意すること（例：配列の添字）。

• 入力の読み込みを高速に行うために sys.stdin.read を使用している。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    S = list(map(int, data[1:N+1]))
    C = list(map(int, data[N+1:N*2]))
    
    # 満足度: (S[0] + ... + S[k-1]) - (C[0] + ... + C[k-2])
    # k=1 のとき、満足度は S[0]
    
    max_satisfaction = S[0]
    current_sum_S = S[0]
    current_sum_C = 0
    
    for k in range(2, N+1):
        current_sum_S += S[k-1]
        current_sum_C += C[k-2]
        satisfaction = current_sum_S - current_sum_C
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。