概要

高橋君がちょうど1科目だけ受け直して得点を自由に変えられるとき、高橋君と青木君の合計得点の差（高橋 − 青木）を最大化する問題です。

考察

まず、受け直しをしない場合の合計得点の差は次のように計算できます。

\[\text{total\_diff} = \sum_{i=1}^{N} A_i - \sum_{i=1}^{N} B_i\]

次に、高橋君が科目 \(i\) を受け直す場合を考えます。科目 \(i\) の得点を \(A_i\) から新しい点数 \(X\)（\(0 \leq X \leq P_i\)）に変更すると、合計得点の差は：

\[\text{total\_diff} - A_i + X\]

になります。これを最大化するには \(X\) をできるだけ大きくすればよいので、\(X = P_i\)（満点）にするのが最適です。

このとき、科目 \(i\) を受け直すことによる「差の増加量（利得）」は：

\[\text{gain}_i = P_i - A_i\]

となります。これは「科目 \(i\) であとどれだけ伸ばせるか」、すなわち 伸びしろ に相当します。

具体例: \(N = 2\)、\(P = [100, 50]\)、\(A = [80, 10]\)、\(B = [70, 60]\) の場合

• 受け直しなしの差: \((80 + 10) - (70 + 60) = -40\)
• 科目1を受け直し: 利得 \(= 100 - 80 = 20\)、差 \(= -40 + 20 = -20\)
• 科目2を受け直し: 利得 \(= 50 - 10 = 40\)、差 \(= -40 + 40 = 0\)

科目2の方が伸びしろが大きいので、科目2を受け直すのが最適です。

重要な気づき: 全科目の中から \(P_i - A_i\) が最大の科目を1つ選べばよいだけなので、全探索で十分効率的です。

アルゴリズム

1. 入力を読み込む。
2. 現在の合計得点の差 \(\text{total\_diff} = \sum A_i - \sum B_i\) を計算する。
3. 各科目 \(i\) について利得 \(P_i - A_i\)（伸びしろ）を計算し、その最大値 \(\text{best\_gain}\) を求める。
4. 答えは \(\text{total\_diff} + \text{best\_gain}\) である。

計算量

• 時間計算量: \(O(N)\) — 合計の計算と最大値の探索がそれぞれ \(O(N)\)
• 空間計算量: \(O(N)\) — 配列 \(P, A, B\) の格納

実装のポイント

• 高橋君は得点を下げることもできますが、差を最大化したいので、必ず満点を取るのが最適です。そのため、得点を下げるケースは考慮不要です。

• \(P_i\) や得点の値が最大 \(10^9\)、科目数が最大 \(2 \times 10^5\) なので、合計値は最大で \(2 \times 10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

• 「受け直した結果、元の点数と同じ点数になることもあり得る」とありますが、これは \(P_i - A_i = 0\) の場合に相当し、利得が 0 になるだけなので自然に処理されます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]; idx += N
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    total_diff = sum(A) - sum(B)
    
    # For each subject i, if Takahashi retakes it, he can change A[i] to any value in [0, P[i]].
    # The new difference = total_diff - A[i] + new_score
    # To maximize, set new_score = P[i], so gain = P[i] - A[i]
    # We want to maximize (P[i] - A[i]) over all i.
    
    best_gain = max(P[i] - A[i] for i in range(N))
    
    print(total_diff + best_gain)

main()

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