各選手について「その選手を絶対的エースにするために必要なトレーニングの回数は？」を考えます。

絶対的エースにしたい選手 \(i\) を固定します。選手 \(i\) 以外をトレーニングするのは損なので、「選手 \(i\) 以外で攻撃力最強の選手」「選手 \(i\) 以外で守備力最強の選手」がそれぞれ分かれば十分です。

「選手 \(i\) 以外で攻撃力最強の選手」を \(i\) ごとに毎回調べていると、\(i\) ごとに \(\Theta(N)\) 、全体で \(\Theta(N^2)\) 掛かってしまい、実行時間制限に間に合わせるのは困難です。

「選手 \(i\) 以外で攻撃力最強の選手」は「全体で攻撃力1位の選手が選手 \(i\) でないなら1位の選手」「全体で攻撃力1位の選手が選手 \(i\) なら2位の選手」なので、\(i\) によらず全選手の1位2位のどちらかです。

よって、予め \(O(N)\) ないし \(O(N\log N)\) で攻撃力・防御力それぞれの 1 位と 2 位の選手を求めておくことで、 \(i\) ごとに \(O(1)\) で最小回数を求めることができるため、全体で \(O(N)\) ないし \(O(N\log N)\) でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for(int i=0; i<n; i++) cin >> a[i] >> b[i];

  vector<int> a_sorted = a, b_sorted = b;
  sort(a_sorted.rbegin(), a_sorted.rend());
  sort(b_sorted.rbegin(), b_sorted.rend());

  int ans=2e9;
  for(int i=0; i<n; i++){
    int tans = 0;
    if(a[i] == a_sorted[0]){
      tans += max(0, a_sorted[1] + 1 - a[i]);
    }else{
      tans += max(0, a_sorted[0] + 1 - a[i]);
    }
    if(b[i] == b_sorted[0]){
      tans += max(0, b_sorted[1] + 1 - b[i]);
    }else{
      tans += max(0, b_sorted[0] + 1 - b[i]);
    }
    ans = min(ans, tans);
  }

  cout << ans << endl;
}

実装例 (Python)

N = int(input())
A = []
B = []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

A_sorted = sorted(A)
B_sorted = sorted(B)

ans = 10**10
for i in range(N):
  tans = 0
  if A[i] == A_sorted[-1]:
    tans += max(0, A_sorted[-2] + 1 - A[i])
  else:
    tans += max(0, A_sorted[-1] + 1 - A[i])
  if B[i] == B_sorted[-1]:
    tans += max(0, B_sorted[-2] + 1 - B[i])
  else:
    tans += max(0, B_sorted[-1] + 1 - B[i])
  ans = min(ans, tans)

print(ans)