概要

\(N\) 科目のテストにおいて、高橋君がちょうど 1 科目だけ自分の得点を書き換えて（\(0\) 点以上満点以下）、高橋君と青木君の合計得点の差（高橋 - 青木）を最大化する問題です。

考察

高橋君の現在の合計得点を \(S_A\)、青木君の現在の合計得点を \(S_B\) とします。現在の得点の差は \(S_A - S_B\) です。

ここで、高橋君が科目 \(i\) の得点を \(A_i\) から \(x\)（\(0 \leq x \leq P_i\)）に変更したとします。このとき、新しい合計得点の差は以下のようになります： $\(\text{(新しい差)} = (S_A - A_i + x) - S_B = (S_A - S_B) + (x - A_i)\)$

この値を最大化するためには、以下の 2 点が重要です。

1. どの値に書き換えるべきか？ 式 \((S_A - S_B) + (x - A_i)\) において、変えられる値は \(x\) と \(i\) です。まず \(i\) を固定して考えると、この値を大きくするには \(x\) をできるだけ大きくすればよいことがわかります。\(x\) の最大値は科目の満点である \(P_i\) なので、\(x = P_i\) とするのが最善です。 このとき、得られる差は \((S_A - S_B) + (P_i - A_i)\) となります。

2. どの科目を選ぶべきか？ 全ての科目 \(i\) について、\(P_i - A_i\)（その科目を満点に書き換えたときに増える得点）を計算し、その値が最大となる科目を選べば、全体の差を最大にすることができます。

もし \(P_i - A_i\) が全ての科目で \(0\)（つまり最初から全ての科目が満点）だったとしても、問題文の「変更後の値としてあり得る最大値」という条件を満たすことができます。

アルゴリズム

1. 現在の高橋君の合計点 \(S_A = \sum A_i\) と、青木君の合計点 \(S_B = \sum B_i\) を計算します。
2. 各科目 \(i = 1, \dots, N\) について、伸び代となる値 \(G_i = P_i - A_i\) を計算します。
3. \(G_i\) の中での最大値 \(max\_gain\) を求めます。
4. \((S_A - S_B) + max\_gain\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 合計点の計算に \(O(N)\)、最大値の探索に \(O(N)\) かかります。\(N \leq 2 \times 10^5\) なので、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された各科目の点数を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• Python では sys.stdin.read().split() を使って一気に入力を読み込むと、データ量が多い場合に高速に処理できます。

• 合計点の計算には組み込み関数の sum() を、最大値の計算には max() を使うことで、簡潔かつ高速に実装できます。

• 今回のコードではループの中で max_gain を更新していますが、max(p[i] - a[i] for i in range(n)) のようにジェネレータ式を使うことも可能です。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 科目数 N を取得
    n = int(data[0])
    
    # 各科目の満点 P_i、高橋君の得点 A_i、青木君の得点 B_i をリストとして取得
    # スライスと map を用いて効率的に整数に変換する
    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() 関数は Python において高速に動作する
    current_diff = sum(a) - sum(b)
    
    # 高橋君はちょうど 1 科目 i を選び、その得点 A_i を 0 以上 P_i 以下の整数 x に変更できる。
    # 合計得点の差を最大化するためには、選んだ科目 i の得点を満点 P_i に変更するのが最善。
    # このとき、合計得点の差は (元の差) + (P_i - A_i) となる。
    # したがって、P_i - A_i が最大となる科目を選べばよい。
    
    max_gain = 0
    for i in range(n):
        gain = p[i] - a[i]
        if gain > max_gain:
            max_gain = gain
            
    # 元の差に最大の増加量を加えたものが答え
    print(current_diff + max_gain)

if __name__ == '__main__':
    solve()

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