概要

チェックポイント \(1\) から \(k\) までの「景観スコアの総和」から「移動コストの総和」を引いた値を「満足度」とし、その最大値を求める問題です。

考察

まず、チェックポイント \(k\) でハイキングを終了したときの満足度を \(f(k)\) とおいて、数式を整理してみましょう。

• \(k=1\) のとき： \(f(1) = S_1\)
• \(k=2\) のとき： \(f(2) = (S_1 + S_2) - C_1\)
• \(k=3\) のとき： \(f(3) = (S_1 + S_2 + S_3) - (C_1 + C_2)\)

このように、各 \(k\) について一から合計を計算すると、1つの \(k\) あたり \(O(k)\) の時間がかかります。すべての \(k\)（\(1\) から \(N\) まで）について計算すると、全体で \(O(N^2)\) の計算量となり、制約の \(N \leq 10^6\) では実行時間制限に間に合いません。

ここで、隣り合うチェックポイントの満足度の差に注目します。 \(f(k)\) と \(f(k-1)\) を比較すると、以下の関係があることが分かります。 $\(f(k) = f(k-1) + S_k - C_{k-1}\)\( つまり、「チェックポイント \)k\( での満足度」は、「前のチェックポイント \)k-1\( での満足度」に「新しく得られるスコア \)Sk\(」を足し、「移動にかかったコスト \)C{k-1}$」を引くだけで求められます。

この性質を利用すれば、前の状態から次の状態を \(O(1)\) で計算できるため、全体で \(O(N)\) の時間で解くことが可能です。

アルゴリズム

1. 満足度の最大値を保持する変数 max_satisfaction と、現在のチェックポイントでの満足度を保持する変数 current_satisfaction を用意し、どちらも \(S_1\) で初期化します。
2. \(i = 2\) から \(N\) まで順番に以下の操作を繰り返します。
   • current_satisfaction に \(S_i\) を加え、\(C_{i-1}\) を引きます。
   • max_satisfaction と current_satisfaction を比較し、大きい方で max_satisfaction を更新します。
3. 最終的な max_satisfaction の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のチェックポイントを一度ずつ走査するため、入力の読み込みを含めて \(N\) に比例した時間で処理が終わります。
• 空間計算量: \(O(N)\)
  • 入力された景観スコア \(S_i\) をリストに保持するため、 \(N\) に比例したメモリを使用します。（工夫次第で \(O(1)\) にすることも可能です）

実装のポイント

• 大きな入力への対応: \(N=10^6\) と入力が非常に多いため、Pythonでは sys.stdin.read().split() やジェネレータなどを使って高速に読み込むのが望ましいです。

• 初期値の設定: \(k=1\) の場合が最小の構成となるため、最大値の初期値は \(0\) ではなく \(S_1\) に設定します。

• 型: スコアやコストの累積和は非常に大きな値（最大 \(10^{15}\) 程度）になりますが、Pythonは標準で多倍長整数を扱うため、オーバーフローの心配はありません。

  ソースコード

import sys
import itertools

def solve():
    # 標準入力からトークン（数値）を1つずつ取得するジェネレータ
    tokens = (token for line in sys.stdin for token in line.split())
    
    # チェックポイントの数 N を取得
    try:
        n_str = next(tokens)
    except StopIteration:
        return
    
    n = int(n_str)
    
    # 景観スコア S_1, S_2, ..., S_N を読み込む
    # 体力コスト C_i が後に続くため、S はリストに格納する必要がある
    s = list(map(int, itertools.islice(tokens, n)))
    
    if not s:
        return
    
    # ハイキングの満足度の最大値を管理する変数
    # 初期値はチェックポイント1で終了した場合の満足度 S_1
    max_satisfaction = s[0]
    current_satisfaction = s[0]
    
    # 残りのトークンは体力コスト C_1, C_2, ..., C_{N-1}
    costs = map(int, tokens)
    
    # チェックポイント k = 2 から N まで順番に満足度を計算
    # チェックポイント k での満足度 f(k) は、f(k-1) + S_k - C_{k-1} で求められる
    # enumerate(costs, 1) により、i は 1 から始まり、s[i] は S_{i+1} に対応する
    for i, cost in enumerate(costs, 1):
        if i >= n:
            break
        # 現在の満足度を更新：前のチェックポイントまでの満足度 + 次の景観スコア - 移動コスト
        current_satisfaction += s[i] - cost
        # 最大値を更新
        if current_satisfaction > max_satisfaction:
            max_satisfaction = current_satisfaction
            
    # 結果を出力
    sys.stdout.write(str(max_satisfaction) + '\n')

if __name__ == '__main__':
    solve()

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