概要

\(N\) 人の選手から1人を選び、その選手の攻撃力と守備力が他の全員より真に大きくなるように能力を上げるとき、必要なトレーニング回数の最小値を求める問題です。

考察

重要な気づき①：他の選手を強化する必要はない

トレーニングでは能力を「上げる」ことしかできません。絶対的エース以外の選手の能力を上げると、エースがそれを上回るためにさらにコストがかかります。よって、エース候補の選手だけを強化すれば十分です。

重要な気づき②：各候補のコスト計算

選手 \(k\) を絶対的エースにしたいとき、必要なコストは次のように計算できます：

• 攻撃力について：\(k\) 以外の選手の攻撃力の最大値を \(M_A\) とすると、\(A_k\) を \(M_A + 1\) 以上にする必要があります。コストは \(\max(0, M_A - A_k + 1)\) です。
• 守備力についても同様に \(\max(0, M_B - B_k + 1)\) です。

例えば、選手が \((A, B) = (3, 5), (7, 2), (5, 4)\) の3人で、選手1（攻撃力3, 守備力5）をエースにしたい場合： - 他の選手の攻撃力の最大値は \(7\) → コスト \(= 7 - 3 + 1 = 5\) - 他の選手の守備力の最大値は \(4\) → コスト \(= \max(0, 4 - 5 + 1) = 0\) - 合計コスト \(= 5\)

素朴なアプローチの問題点

各候補 \(k\) に対して「\(k\) 以外の最大値」を毎回 \(O(N)\) で計算すると、全体で \(O(N^2)\) となり、\(N \leq 2 \times 10^5\) では TLE になります。

解決法：上位2つを記録する

攻撃力・守備力それぞれについて、全体の最大値（1位）と2番目の値（2位）を事前に求めておけば、「\(k\) を除いた最大値」を \(O(1)\) で求められます：

• \(k\) が最大値を持つ選手なら → 2位の値が「\(k\) を除いた最大値」
• そうでなければ → 1位の値がそのまま「\(k\) を除いた最大値」

アルゴリズム

1. 攻撃力 \(A\) について、最大値とそのインデックス、および2番目に大きい値を求める。
2. 守備力 \(B\) についても同様に求める。
3. 各選手 \(k = 0, 1, \ldots, N-1\) に対して：
   • \(k\) を除いた攻撃力の最大値 \(M_A\) を \(O(1)\) で取得
   • \(k\) を除いた守備力の最大値 \(M_B\) を \(O(1)\) で取得
   • コスト \(= \max(0, M_A - A_k + 1) + \max(0, M_B - B_k + 1)\)
4. 全候補のコストの最小値を出力する。

計算量

• 時間計算量: \(O(N)\)（上位2つの前計算に \(O(N)\)、各候補のコスト計算に \(O(N)\)）
• 空間計算量: \(O(N)\)（入力の格納）

実装のポイント

• 上位2つを求める際、最大値を持つ選手が複数いる場合にも正しく動くよう注意が必要です。コード中では a_max1_idx に最大値を持つ選手の1つのインデックスを記録し、候補 \(k\) がそのインデックスと一致するかで場合分けしています。最大値が複数の選手に存在する場合、2位の値は1位と同じになるため、この方法で正しく処理できます。

• max(0, ...) を取ることで、既にエース候補の能力が十分高い場合にコスト0となるようにしています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i] = int(input_data[idx]); idx += 1
        B[i] = int(input_data[idx]); idx += 1
    
    # For each candidate k to be the absolute ace:
    # We need A[k] > A[j] and B[k] > B[j] for all j != k
    # We can only increase values, not decrease.
    # Cost = sum over j != k of max(0, A[j] - A[k] + 1) if A[j] >= A[k], but wait...
    # 
    # Actually, we need A[k]' > A[j]' and B[k]' > B[j]' for all j != k
    # where primed values are after training (only increases allowed).
    # 
    # The optimal strategy: pick candidate k, then set A[k]' = max of all A values (if needed) + handle ties,
    # and B[k]' = max of all B values (if needed) + handle ties.
    # But we can also increase OTHER players? No wait - we want k to be STRICTLY greater than all others.
    # We can only INCREASE values. So increasing others makes it harder, not easier.
    # Therefore we'd never increase other players' stats.
    # 
    # So the cost for candidate k is:
    # cost_A = max(0, max(A[j] for j != k) - A[k] + 1)  (need A[k]' > max A[j] for j!=k)
    # cost_B = max(0, max(B[j] for j != k) - B[k] + 1)
    # total cost for k = cost_A + cost_B
    #
    # We want to minimize over all k.
    
    # Precompute: for A, we need max of A excluding k.
    # We can do this by finding the top 2 values of A and top 2 values of B.
    
    # Find top 2 for A
    a_max1 = -1
    a_max1_idx = -1
    a_max2 = -1
    for i in range(N):
        if A[i] > a_max1:
            a_max2 = a_max1
            a_max1 = A[i]
            a_max1_idx = i
        elif A[i] > a_max2:
            a_max2 = A[i]
    
    # Find top 2 for B
    b_max1 = -1
    b_max1_idx = -1
    b_max2 = -1
    for i in range(N):
        if B[i] > b_max1:
            b_max2 = b_max1
            b_max1 = B[i]
            b_max1_idx = i
        elif B[i] > b_max2:
            b_max2 = B[i]
    
    ans = float('inf')
    for k in range(N):
        # max A excluding k
        if k == a_max1_idx:
            max_a_others = a_max2
        else:
            max_a_others = a_max1
        
        # max B excluding k
        if k == b_max1_idx:
            max_b_others = b_max2
        else:
            max_b_others = b_max1
        
        cost_a = max(0, max_a_others - A[k] + 1)
        cost_b = max(0, max_b_others - B[k] + 1)
        
        total = cost_a + cost_b
        if total < ans:
            ans = total
    
    print(ans)

solve()

---

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