概要

\(N\) 人の選手の中から 1 人を「絶対的エース」にするために必要な、トレーニング回数（能力値の加算合計）の最小値を求める問題です。 ある選手が絶対的エースであるとは、その選手の攻撃力と守備力の両方が、自分以外の他のどの選手よりも真に大きい状態を指します。

考察

絶対的エースの条件

選手 \(i\) を絶対的エースにするためには、以下の 2 つの条件を同時に満たす必要があります。 1. 選手 \(i\) の攻撃力 \(A_i\) が、自分以外の全選手の攻撃力の最大値よりも大きい（\(A_i > \max_{j \neq i} A_j\)） 2. 選手 \(i\) の守備力 \(B_i\) が、自分以外の全選手の守備力の最大値よりも大きい（\(B_i > \max_{j \neq i} B_j\)）

つまり、目標とする攻撃力は \(\max_{j \neq i} A_j + 1\)、目標とする守備力は \(\max_{j \neq i} B_j + 1\) となります。現在の能力値がすでにこの値以上であれば、トレーニングは不要です。

効率的な最大値の求め方

各選手 \(i\) について「自分以外の最大値」を素直に求めようとすると、毎回 \(N-1\) 人をチェックすることになり、全体で \(O(N^2)\) の計算量がかかります。\(N = 2 \times 10^5\) であるため、これでは制限時間に間に合いません。

そこで、あらかじめチーム全体の最大値、最大値を持つ人数、および2 番目に大きい値を求めておくことで、各選手の「自分以外の最大値」を \(O(1)\) で判定できます。

• 選手 \(i\) の能力値がチーム全体の最大値ではない場合： 自分以外の最大値は、チーム全体の最大値と一致します。
• 選手 \(i\) の能力値がチーム全体の最大値である場合：
  • 最大値を持つ人が自分以外にもいるなら、自分以外の最大値はチーム全体の最大値と同じです。
  • 最大値を持つ人が自分一人だけなら、自分以外の最大値はチーム全体の「2 番目に大きい値」になります。

アルゴリズム

1. 攻撃力 \(A\) と守備力 \(B\) のそれぞれについて、以下の情報を走査して取得します。
   • 最大値 (\(max1\))
   • 2 番目に大きい値 (\(max2\))
   • 最大値をとる要素の個数 (\(count1\))
2. 各選手 \(i = 1, \dots, N\) について、以下の手順でコストを計算します。
   • 攻撃力の必要コスト:
     • \(A_i\) が唯一の最大値なら、目標値は \(max2_A + 1\)。
     • そうでなければ、目標値は \(max1_A + 1\)。
     • コストは \(\max(0, \text{目標値} - A_i)\)。
   • 守備力の必要コスト:
     • \(B_i\) が唯一の最大値なら、目標値は \(max2_B + 1\)。
     • そうでなければ、目標値は \(max1_B + 1\)。
     • コストは \(\max(0, \text{目標値} - B_i)\)。
   • 合計コスト = 攻撃力のコスト + 守備力のコスト
3. 全選手の中での合計コストの最小値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 最大値などの情報を得るための走査に \(O(N)\)、各選手のコスト計算のためのループに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 全選手の能力値を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 最大値情報の取得: 1 回の走査で \(max1, max2, count1\) を同時に求める関数を作成すると効率的です。

• 入力の高速化: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むのが定石です。

• 2 番目の最大値の初期値: 能力値は 1 以上なので、初期値を 0 や -1 にしておくことで、選手が 2 人以上いれば正しく更新されます。

  ソースコード

import sys

def solve():
    # Fast input reading: read everything at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        line1 = next(it)
    except StopIteration:
        return
        
    N = int(line1)
    
    # Pre-allocate lists for attack (A) and defense (B) to save memory and time
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i] = int(next(it))
        B[i] = int(next(it))
        
    # Helper function to find the maximum value, the second maximum (among other players),
    # and the count of the maximum value in one pass.
    def get_max_info(arr):
        m1 = -1
        m2 = -1
        count1 = 0
        for x in arr:
            if x > m1:
                m2 = m1
                m1 = x
                count1 = 1
            elif x == m1:
                count1 += 1
            elif x > m2:
                m2 = x
        return m1, m2, count1

    # Get statistics for both attack and defense
    max_a1, max_a2, count_a1 = get_max_info(A)
    max_b1, max_b2, count_b1 = get_max_info(B)
    
    min_total_cost = float('inf')
    
    # Iterate through each player to calculate the cost to make them the absolute ace
    for i in range(N):
        # To be an absolute ace, player i must have A[i] > max(A[j] for j != i)
        # and B[i] > max(B[j] for j != i).
        
        # Calculate the maximum attack value among other players
        if A[i] == max_a1:
            if count_a1 > 1:
                # There is another player with the same maximum attack
                other_max_a = max_a1
            else:
                # Player i is the unique maximum, the next highest is max_a2
                other_max_a = max_a2
        else:
            # Player i is not a maximum, so the maximum of others is max_a1
            other_max_a = max_a1
        
        # Calculate the maximum defense value among other players
        if B[i] == max_b1:
            if count_b1 > 1:
                other_max_b = max_b1
            else:
                other_max_b = max_b2
        else:
            other_max_b = max_b1
            
        # Target values must be strictly greater than the others
        target_a = other_max_a + 1
        target_b = other_max_b + 1
        
        # Calculate training sessions needed (cannot be negative)
        cost_a = target_a - A[i]
        if cost_a < 0:
            cost_a = 0
            
        cost_b = target_b - B[i]
        if cost_b < 0:
            cost_b = 0
            
        # Update the minimum total training sessions across all candidates
        current_cost = cost_a + cost_b
        if current_cost < min_total_cost:
            min_total_cost = current_cost
                
    # Output the final result
    print(min_total_cost)

if __name__ == '__main__':
    solve()

---

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