概要

チェックポイントごとの景観スコアと移動コストが与えられ、適切な終了地点を選んで満足度（景観スコアの累積和から移動コストの累積和を引いた値）を最大化する問題です。

考察

各チェックポイント \(k\) での満足度は、\((\sum_{i=1}^{k} S_i) - (\sum_{i=1}^{k-1} C_i)\) で計算できます。素朴なアプローチでは、すべての \(k\) について満足度を計算して最大値を求めることが考えられますが、\(N\) が最大 \(10^6\) と大きいため、累積和を事前計算せずに毎回計算すると時間計算量が \(O(N^2)\) となり、実行時間制限に間に合いません。

この問題では、チェックポイント1から順に進みながら、現在の満足度を更新していくことで効率的に解くことができます。各地点での満足度は、直前の地点での満足度に現在の景観スコア \(S_i\) を加え、移動コスト \(C_{i-1}\) を引くことで計算できるため、時間計算量 \(O(N)\) で解けます。

アルゴリズム

1. チェックポイント1での満足度 \(S_1\) を初期値として設定
2. チェックポイント2からNまで順に処理：
   • 現在の満足度 = 直前の満足度 + \(S_i\) - \(C_{i-1}\)
   • 現在の満足度が最大値を超えていれば更新
3. 得られた最大満足度を出力

この手法は、満足度の計算が漸化式的に表現できることを利用しています。つまり、\(k\) 地点での満足度 \(F(k)\) は \(F(k) = F(k-1) + S_k - C_{k-1}\) で計算できます（ただし \(F(1) = S_1\)）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力データを一度に読み込んで処理する

• \(N=1\) の場合は移動コストが存在しないため、特別扱いする

• 現在の満足度と最大満足度を変数で保持しながら1回のループで処理する

• 各ステップで最大値の更新チェックを忘れない

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    S = list(map(int, data[1:1+n]))
    if n == 1:
        print(S[0])
        return
        
    C = list(map(int, data[1+n:1+n+(n-1)]))
    
    current_sum = S[0]
    max_satisfaction = current_sum
    
    for i in range(1, n):
        current_sum = current_sum + S[i] - C[i-1]
        if current_sum > max_satisfaction:
            max_satisfaction = current_sum
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。