概要

山道のハイキングコースで、どのチェックポイントまで進めば「景観スコアの合計 − 体力コストの合計」が最大になるかを求める問題です。累積的に満足度を計算しながら、その最大値を追跡すればよいです。

考察

問題の整理

チェックポイント \(k\) で終了したときの満足度は次の式で表されます：

\[f(k) = \sum_{i=1}^{k} S_i - \sum_{i=1}^{k-1} C_i\]

すべての \(k\)（\(1 \leq k \leq N\)）について \(f(k)\) を計算し、その最大値を求めたいです。

重要な気づき：逐次的に計算できる

\(f(k)\) と \(f(k+1)\) の関係を見てみましょう：

\[f(k+1) = \sum_{i=1}^{k+1} S_i - \sum_{i=1}^{k} C_i = f(k) + S_{k+1} - C_k\]

つまり、\(f(k)\) がわかっていれば、\(S_{k+1} - C_k\) を足すだけで \(f(k+1)\) が求まります。

具体例

例えば \(N=4\)、\(S = [10, 3, 8, 2]\)、\(C = [5, 6, 1]\) の場合：

\(k\)	満足度 \(f(k)\)	計算
1	\(10\)	\(S_1 = 10\)
2	\(10 - 5 + 3 = 8\)	\(f(1) - C_1 + S_2\)
3	\(8 - 6 + 8 = 10\)	\(f(2) - C_2 + S_3\)
4	\(10 - 1 + 2 = 11\)	\(f(3) - C_3 + S_4\)

最大値は \(f(4) = 11\) です。

素朴なアプローチとの比較

毎回 \(f(k)\) を最初から計算し直すと \(O(N^2)\) かかり、\(N \leq 10^6\) ではTLEになります。逐次的に更新すれば \(O(N)\) で済みます。

アルゴリズム

1. \(\text{current} = S_1\)（チェックポイント1での満足度）、\(\text{best} = S_1\) と初期化する。
2. \(i = 2, 3, \ldots, N\) の順に以下を行う：
   • \(\text{current} = \text{current} - C_{i-1} + S_i\) と更新する。
   • \(\text{current} > \text{best}\) なら \(\text{best} = \text{current}\) と更新する。
3. 最終的な \(\text{best}\) を出力する。

これは、各チェックポイントでの満足度を逐次的に求めつつ、最大値を記録していく「走査しながら最大値を管理する」典型パターンです。

計算量

• 時間計算量: \(O(N)\) — 配列を一度走査するだけ
• 空間計算量: \(O(N)\) — 入力の \(S\) と \(C\) を配列に格納する分（逐次読み込みにすれば \(O(1)\) も可能）

実装のポイント

• sys.stdin.read() で高速入力: \(N\) が最大 \(10^6\) と大きいので、Pythonでは input() を繰り返すより sys.stdin.read() で一括読み込みしてから split() する方が高速です。

• \(N = 1\) の場合: ループが実行されず best = S[0] がそのまま答えになるので、特別な場合分けは不要です。

• オーバーフロー: \(S_i, C_i\) が最大 \(10^9\)、\(N\) が最大 \(10^6\) なので、満足度は最大で約 \(10^{15}\) 程度になりますが、Pythonは多倍長整数を扱えるため問題ありません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(N - 1)]; idx += N - 1

    current = S[0]
    best = current
    for i in range(1, N):
        current = current - C[i - 1] + S[i]
        if current > best:
            best = current
    print(best)

main()

---

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