概要

社員の集合 \(S\) を選び、\(\min(\sum_{i \in S} A_i, \sum_{i \in S} B_i)\) を最大化する問題です。
各能力値はすべて正なので、最適な選び方は「全員を選ぶ」ことになります。

考察

選んだ社員集合 \(S\) に対して、チームの総合力は

\(\min(\sum_{i \in S} A_i, \sum_{i \in S} B_i)\)

です。

ここで重要なのは、制約よりすべての \(A_i, B_i\) が正の整数であることです。

つまり、ある社員をチームに追加すると、

• プログラミング能力の合計は必ず増える
• デザイン能力の合計も必ず増える

という性質があります。

例えば、現在の合計が

• プログラミング能力の合計: \(X\)
• デザイン能力の合計: \(Y\)

であるとします。社員 \(i\) を追加すると、

• プログラミング能力の合計: \(X + A_i\)
• デザイン能力の合計: \(Y + B_i\)

になります。

ここで \(A_i > 0, B_i > 0\) なので、どちらの合計も増えます。
したがって、

\(\min(X + A_i, Y + B_i) \geq \min(X, Y)\)

が成り立ちます。

つまり、社員を追加しても総合力が下がることはありません。

そのため、総合力を最大化するには、選べる社員をすべて選べばよいです。

素朴にすべての部分集合を試すと、社員ごとに「選ぶ・選ばない」の \(2\) 通りがあるため、全体で \(2^N\) 通りになります。
\(N \leq 2 \times 10^5\) なので、これは到底間に合いません。

しかし、上の性質により、部分集合を探索する必要はなく、全員を選んだときの値を計算するだけで十分です。

アルゴリズム

全員をチームに入れるとき、

• プログラミング能力の合計を \(\sum_{i=1}^{N} A_i\)
• デザイン能力の合計を \(\sum_{i=1}^{N} B_i\)

とします。

答えはこの小さい方なので、

\(\min(\sum_{i=1}^{N} A_i, \sum_{i=1}^{N} B_i)\)

を出力します。

手順は以下の通りです。

1. 入力を受け取る
2. すべての \(A_i\) の合計を求める
3. すべての \(B_i\) の合計を求める
4. その小さい方を出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

入力は

N
A_1 B_1
A_2 B_2
...
A_N B_N

という形式です。

コードでは入力全体を整数のリスト data として読み込んでいます。

data = list(map(int, sys.stdin.buffer.read().split()))

このとき、data は次のように並びます。

[N, A_1, B_1, A_2, B_2, ..., A_N, B_N]

したがって、

data[1::2]

で \(A_1, A_2, ..., A_N\) を取り出せます。

また、

data[2::2]

で \(B_1, B_2, ..., B_N\) を取り出せます。

それぞれの合計を求めて、小さい方を出力します。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    sum_a = sum(data[1::2])
    sum_b = sum(data[2::2])
    print(min(sum_a, sum_b))

if __name__ == "__main__":
    main()

---

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