概要

高橋君はちょうど1科目の得点を変更することで、自分の合計得点と青木君の合計得点の差を最大にしたいと思っています。この差の最大値を求めましょう。

考察

この問題では、高橋君がちょうど1つの科目について得点を変えられますが、他の科目の得点は固定されます。また、青木君の得点もすべて固定されています。
したがって、高橋君の目標は「1科目だけ変更して、合計得点の差 $\((\text{高橋君の合計}) - (\text{青木君の合計})\)$ を最大化すること」です。

各科目の選択肢

ある科目 \(i\) において、高橋君が得点を変更できる範囲は \(0\) 点〜 \(P_i\) 点の間です。つまり、その科目での得点を： - 最小値 \(0\) に変更する - 最大値 \(P_i\) に変更する

のどちらかを選ぶのが最も効果的です。なぜなら、それ以外の中間的な値を選んでも、差をさらに大きくすることはできないからです。

素朴なアプローチとその問題点

素朴には、すべての科目に対して、得点を \(0\) から \(P_i\) のすべて試すという方法がありますが、これは計算量的に無理があります（特に \(P_i\) が大きい場合）。
しかし、実際には各科目について「最小値にするか」「最大値にするか」の2択だけを考えれば十分です。

差の変化に注目

今、高橋君の元の合計得点を \(S_A = \sum_{i=1}^{N} A_i\)、青木君の合計得点を \(S_B = \sum_{i=1}^{N} B_i\) とします。
科目 \(i\) の得点を変更するとき： - 得点を \(0\) にすると、新しい合計は \(S_A - A_i\) になり、差は \((S_A - A_i) - S_B\) - 得点を \(P_i\) にすると、新しい合計は \(S_A - A_i + P_i\) になり、差は \((S_A - A_i + P_i) - S_B\)

この2つのうち大きい方を選ぶのが最適です。

最初の差 \(S_A - S_B\) も候補になるので、最終的にはすべての科目について上記の操作を行ったときの最大値が答えになります。

アルゴリズム

1. 高橋君と青木君の合計得点 \(S_A\), \(S_B\) を求める。
2. 最初の差 \(D = S_A - S_B\) を保持しておく。
3. 各科目 \(i\) に対して以下を行う：
   • 科目 \(i\) の得点を \(0\) に変更したときの差：\(D - A_i\)
   • 科目 \(i\) の得点を \(P_i\) に変更したときの差：\(D - A_i + P_i\)
   • この2つのうち大きい方を候補として、全体の最大値を更新していく。
4. 全ての科目を調べた後、得られた最大値を出力する。

計算量

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

※ 各科目につき定数時間で処理できるため、線形時間で解けます。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している（Pythonの場合）。
• 各科目について、得点を0または満点に変更した場合の差を比較し、最大値を更新していく。
• 最初の差も初期値として考慮することを忘れない。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    P = list(map(int, data[1:N+1]))
    A = list(map(int, data[N+1:2*N+1]))
    B = list(map(int, data[2*N+1:3*N+1]))
    
    # 高橋君の現在の合計点
    sum_A = sum(A)
    # 青木君の合計点（固定）
    sum_B = sum(B)
    
    max_diff = sum_A - sum_B  # 最初の差
    
    for i in range(N):
        # 高橋君がi番目の科目を0点に変更した場合の差
        diff_if_zero = (sum_A - A[i]) - sum_B
        # 高橋君がi番目の科目をP[i]点に変更した場合の差
        diff_if_max = (sum_A - A[i] + P[i]) - sum_B
        # その科目を変更することで得られる最大の差
        new_diff = max(diff_if_zero, diff_if_max)
        if new_diff > max_diff:
            max_diff = new_diff
            
    print(max_diff)

if __name__ == "__main__":
    main()

---

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