概要

各選手を「絶対的エース」にすると仮定したとき、他の全員より攻撃力・守備力の両方を 必ず 1 以上上回るために必要な増加回数を計算し、その最小値を求めます。

考察

ある選手 \(i\) をエースにするには、すべての \(j \neq i\) に対して - \(A_i > A_j\) - \(B_i > B_j\)

が必要です。トレーニングでできるのは増加のみなので、結局

• \(A_i\) は「他の選手の攻撃力最大値」より 1 大きいところまで上げる
• \(B_i\) も同様

にすれば十分で、必要回数は次で求まります：

• 必要攻撃上げ回数：\(\max(0, (\max_{j\neq i} A_j) + 1 - A_i)\)
• 必要守備上げ回数：\(\max(0, (\max_{j\neq i} B_j) + 1 - B_i)\)

合計が、その選手をエースにする最小回数です。

素朴解がダメな理由

各 \(i\) について \(\max_{j\neq i} A_j\) や \(\max_{j\neq i} B_j\) を愚直に求めると、1人ごとに \(O(N)\) かかり合計 \(O(N^2)\) になってしまい、\(N \le 2\times 10^5\) では間に合いません。

重要な気づき

必要なのは「除外した最大値」だけです。これは各パラメータについて - 最大値（top1） - 最大値の個数 - 2番目の最大値（top2）

を持っておけば、各選手 \(i\) に対する \(\max_{j\neq i}\) を \(O(1)\) で求められます。

例えば攻撃力について： - もし選手 \(i\) が最大値 \(maxA1\) を 唯一持っているなら、除外後の最大は \(maxA2\) - そうでなければ（最大値でない、または最大値が複数人いる）、除外後の最大は \(maxA1\)

守備力も同様です。

アルゴリズム

1. 攻撃力配列 \(A\) から \((maxA1, cntA1, maxA2)\) を求める
   
   • \(maxA1\): 最大値
     
   • \(cntA1\): 最大値の個数
     
   • \(maxA2\): 2番目の最大値
2. 守備力配列 \(B\) から \((maxB1, cntB1, maxB2)\) を求める
3. 各選手 \(i\) について以下を計算する：
   • 他選手の攻撃最大値 \(maxA\_ex\)
     • \(A_i\) が \(maxA1\) かつ \(cntA1=1\) なら \(maxA2\)
     • それ以外は \(maxA1\)
   • 他選手の守備最大値 \(maxB\_ex\) も同様
   • 必要回数
     \(needA = \max(0, maxA\_ex + 1 - A_i)\)
     \(needB = \max(0, maxB\_ex + 1 - B_i)\)
     合計 \(needA + needB\)
4. その最小値を答えとして出力する。

簡単な例

攻撃力が \([5, 3, 5]\) のとき、最大値は 5 で 2人いるので、5の選手を除外しても他に 5 が残ります。
つまりその選手がエースになるには、攻撃力は \(5+1=6\) まで上げる必要があります（同値ではダメで「真に大きい」が必要）。

計算量

• 時間計算量: \(O(N)\)（最大・2番目最大の計算と全選手走査）
• 空間計算量: \(O(N)\)（入力を配列として保持）

実装のポイント

• 「除外後の最大値」を正しく出すには、最大値が何回出現するかが重要です（1回なら2番目最大、複数回なら最大のまま）。

• 条件は「以上」ではなく「より大きい」なので、目標は常に \((最大値)+1\) です。

• \(A_i, B_i\) は最大 \(10^9\) なので、計算は Python の int で安全ですが、答えの初期値は十分大きく（コードでは \(10^{30}\)）しておくと安心です。

  ソースコード

import sys

def two_max(values):
    max1 = -1
    max2 = -1
    cnt1 = 0
    for x in values:
        if x > max1:
            max2 = max1
            max1 = x
            cnt1 = 1
        elif x == max1:
            cnt1 += 1
        elif x > max2:
            max2 = x
    return max1, cnt1, max2

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    A = [0] * n
    B = [0] * n
    idx = 1
    for i in range(n):
        A[i] = data[idx]
        B[i] = data[idx + 1]
        idx += 2

    maxA1, cntA1, maxA2 = two_max(A)
    maxB1, cntB1, maxB2 = two_max(B)

    ans = 10**30
    for i in range(n):
        maxA_ex = maxA1 if (A[i] != maxA1 or cntA1 > 1) else maxA2
        maxB_ex = maxB1 if (B[i] != maxB1 or cntB1 > 1) else maxB2

        needA = max(0, maxA_ex + 1 - A[i])
        needB = max(0, maxB_ex + 1 - B[i])
        ans = min(ans, needA + needB)

    print(ans)

if __name__ == "__main__":
    main()

---

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