概要

本問題は、与えられた社員の中からチームメンバーを選び、プログラミング能力の合計とデザイン能力の合計の最小値を最大化する問題です。 一見すると、どの社員を選ぶべきか選別する必要があるように思えますが、実は「全員を選ぶ」ことが常に最適解となります。

考察

各社員の能力値 \(A_i, B_i\) はすべて \(1\) 以上の正の整数です。 選んだ社員の集合を \(S\) としたとき、総合力は \(\min\left(\sum_{i \in S} A_i, \sum_{i \in S} B_i\right)\) と定義されます。

ここで、ある社員のグループ \(S\) に、まだ選ばれていない社員 \(j\) を追加することを考えます。 社員 \(j\) を追加した後のグループを \(S' = S \cup \{j\}\) とします。 このとき、プログラミング能力の合計とデザイン能力の合計は以下のように変化します。 - プログラミング能力の合計: \(\sum_{i \in S'} A_i = \left(\sum_{i \in S} A_i\right) + A_j\) - デザイン能力の合計: \(\sum_{i \in S'} B_i = \left(\sum_{i \in S} B_i\right) + B_j\)

\(A_j \ge 1\) かつ \(B_j \ge 1\) であるため、社員を追加するとプログラミング能力の合計もデザイン能力の合計も必ず増加します。 合計値がどちらも増加するということは、その最小値である \(\min\left(\sum A_i, \sum B_i\right)\) も必ず増加します。

具体例

あるグループ \(S\) の能力の合計が (プログラミング, デザイン) = \((10, 15)\) だったとします。このときの総合力は \(\min(10, 15) = 10\) です。 ここに能力 \((A_j, B_j) = (3, 2)\) の社員を追加すると、新しい合計は \((13, 17)\) になり、総合力は \(\min(13, 17) = 13\) となって、追加前よりも大きくなります。

このように、メンバーを追加すればするほど総合力は高くなるため、総合力を最大化するためには全員をチームに選ぶのが最適です。

アルゴリズム

1. 与えられたすべての社員のプログラミング能力の総和 \(sum\_A = \sum_{i=1}^N A_i\) を計算します。
2. 同様に、すべての社員のデザイン能力の総和 \(sum\_B = \sum_{i=1}^N B_i\) を計算します。
3. \(\min(sum\_A, sum\_B)\) を出力します。

計算量

• 時間計算量: \(O(N)\) 全員の能力値を \(1\) 回ずつ走査して合計を求めるため、時間計算量は社員の数 \(N\) に比例します。制約 \(N \le 2 \times 10^5\) に対し、十分に高速に動作します。
• 空間計算量: \(O(N)\) 提供されたコードでは入力を一括で取得してリストに格納しているため、空間計算量は \(O(N)\) となります。

実装 of ポイント

• 入力数が最大で \(2 \times 10^5\) 行と多いため、Pythonでは sys.stdin.read().split() を用いて一括で入力を読み込むことで、高速に入力処理を行うことができます。

• 答えの数値が非常に大きくなる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローの心配はありません。C++などの他言語で実装する場合は、合計値が 64bit 整数型（long longなど）に収まるように注意する必要があります。

  ソースコード

import sys

def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    sum_A = 0
    sum_B = 0
    
    # 各社員の能力値を合計する
    for i in range(N):
        sum_A += int(input_data[2 * i + 1])
        sum_B += int(input_data[2 * i + 2])
        
    # 全員を選んだときが常に総合力が最大となる
    print(min(sum_A, sum_B))

if __name__ == '__main__':
    main()

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