概要

高橋君の合計点と青木君の合計点の差を、ちょうど1科目だけ高橋君の点数を変更して最大化します。結論として「差の初期値」に「1科目で増やせる最大増分」を足せば答えになります。

考察

まず、変更前の合計点の差を
\(D=\sum_i A_i-\sum_i B_i\)
とおきます。

高橋君が科目 \(i\) を受け直し、点数を \(A_i'\) に変えると、差は [ D’ = \left(\sum_{j\ne i} A_j + A_i’\right) - \sum_j B_j = D + (A_i’ - A_i) ] となります。つまり、差を最大化するには \((A_i' - A_i)\) を最大にする科目を1つ選べばよい です。

ここで \(A_i'\) は \(0\) 以上 \(P_i\) 以下の任意の整数なので、\((A_i' - A_i)\) を最大にするにはその科目を満点にすればよく、 [ \max (A_i’ - A_i) = P_i - A_i ] です。

よって全体としては - 初期差 \(D\) - 各科目での増分 \(P_i - A_i\) の最大値

を求めて、\(D + \max_i (P_i - A_i)\) が答えです。

素朴に「各科目を選んで、変更後の合計点を毎回計算し直す」こともできますが、そのままだと1回の計算に \(O(N)\)、それを \(N\) 回で \(O(N^2)\) となり、\(N\le 2\times 10^5\) では間に合いません。上の変形で「増える分だけ見ればよい」と気づくことで \(O(N)\) に落とせます。

（例） \(P=[100,50], A=[60,40]\) なら増分は \([40,10]\) なので最大増分は \(40\)。
初期差 \(D\) に \(40\) を足したものが最大です。

アルゴリズム

1. \(D=\sum_i A_i-\sum_i B_i\) を計算する。
2. 各科目について増分 \(P_i-A_i\) を計算し、その最大値 \(best\_inc=\max_i(P_i-A_i)\) を求める。
3. \(D+best\_inc\) を出力する。

計算量

• 時間計算量: \(O(N)\)（合計と最大値をそれぞれ1回ずつ走査）
• 空間計算量: \(O(1)\)（入力配列を除けば定数。Python実装では配列保持分は \(O(N)\)）

実装のポイント

• 「1科目だけ変更」は「変更しない」も許されますが、\(P_i-A_i\ge 0\) なので最大増分は必ず非負になり、自然に条件を満たします。

• 増分は max(p - a for p, a in zip(P, A)) のように1回の走査で求められます。

• \(P_i\) が大きいので、合計や差は int（Pythonなら自動で多倍長）で安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    diff = sum(A) - sum(B)
    best_inc = max(p - a for p, a in zip(P, A))
    print(diff + best_inc)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。