概要

この問題は、高橋君が1科目だけ得点を変更できるとき、高橋君の合計得点から青木君の合計得点を引いた値の最大値を求める問題です。

考察

まず、何も変更しない場合の合計得点の差は \(base = \sum_{i=1}^{N} A_i - \sum_{i=1}^{N} B_i\) で計算できます。ここで、科目 \(i\) のみを変更する場合を考えます。科目 \(i\) を変更すると、元の差 \(base\) から \((A_i - B_i)\) の分が一旦引かれ、新しい得点 \(x\) と青木君の得点 \(B_i\) の差 \((x - B_i)\) が加わります。つまり、変更後の差は \(base - (A_i - B_i) + (x - B_i)\) となります。\(x\) は \(0\) 以上 \(P_i\) 以下の整数なので、最大値は \(x = P_i\) のとき、つまり \(base - (A_i - B_i) + (P_i - B_i)\) となります。したがって、各科目についてこの値を計算し、その最大値を求めれば良いです。

アルゴリズム

1. 何も変更しない場合の合計得点の差 \(base\) を計算する。
2. 各科目 \(i\) について、変更後の最大の差 \(base - (A_i - B_i) + (P_i - B_i)\) を計算する。
3. 全ての科目について計算した値の最大値を求める。

計算量

• 時間計算量: \(O(N)\)
  • 合計の計算に \(O(N)\)、各科目の計算に \(O(N)\) なので、全体で \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 入力の配列を保存するためです。

実装のポイント

• 初期値の \(max_diff\) は非常に小さい値（\(-10^{18}\)）に設定しています。これは、計算結果が負になる可能性があるためです。

• 各科目について、式をそのまま計算すれば良いので、実装はシンプルです。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1:1+n]))
    A = list(map(int, data[1+n:1+2*n]))
    B = list(map(int, data[1+2*n:1+3*n]))
    
    base = sum(A) - sum(B)
    
    max_diff = -10**18
    for i in range(n):
        current_diff = base - (A[i] - B[i])
        max_possible = current_diff + P[i] - B[i]
        max_diff = max(max_diff, max_possible)
    
    print(max_diff)

if __name__ == "__main__":
    main()

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