概要

\(N\) 人の社員から部分集合を選び、プログラミング能力の合計とデザイン能力の合計の小さい方（総合力）を最大化する問題です。結論として、全員を選ぶのが最適です。

考察

重要な気づき：全員を選ぶのが常に最適

この問題の最大のポイントは、能力値がすべて正（\(A_i \geq 1, B_i \geq 1\)）であるという制約です。

現在のチーム \(S\) に対して、まだ選ばれていない社員 \(j\) を追加することを考えます：

• プログラミング能力の合計: \(\sum A_i \to \sum A_i + A_j\)（\(A_j > 0\) なので増加）
• デザイン能力の合計: \(\sum B_i \to \sum B_i + B_j\)（\(B_j > 0\) なので増加）

両方の合計が増加するので、その小さい方の値（= 総合力）も必ず増加します。

具体例

例えば社員が3人で \((A, B) = (5, 3), (2, 6), (1, 4)\) のとき：

選んだ社員	\(\sum A\)	\(\sum B\)	総合力 \(= \min\)
{1}	5	3	3
{1, 2}	7	9	7
{1, 2, 3}	8	13	8

人を追加するたびに総合力が上がっていくことが分かります。

素朴なアプローチが不要な理由

全 \(2^N - 1\) 通りの部分集合を探索する必要はありません。上記の考察から、全員を選ぶ 一択であることが証明できるため、単に全員の合計を計算すればよいのです。

アルゴリズム

1. 全社員のプログラミング能力の合計 \(\text{sumA} = \sum_{i=1}^{N} A_i\) を計算する
2. 全社員のデザイン能力の合計 \(\text{sumB} = \sum_{i=1}^{N} B_i\) を計算する
3. \(\min(\text{sumA}, \text{sumB})\) を出力する

計算量

• 時間計算量: \(O(N)\)（全社員の能力値を1回ずつ読み取り、合計を計算するだけ）
• 空間計算量: \(O(1)\)（合計値を保持する変数のみ）

実装のポイント

• \(N\) が最大 \(2 \times 10^5\)、各能力値が最大 \(10^9\) なので、合計値は最大 \(2 \times 10^{14}\) 程度になります。int では溢れるため、long long を使う必要があります。

• 問題の本質は「全員選ぶのが最適」という数学的な観察にあり、実装自体は非常にシンプルです。

  ソースコード

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

int main() {
    int n;
    cin >> n;
    long long sumA = 0, sumB = 0;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        sumA += a;
        sumB += b;
    }
    cout << min(sumA, sumB) << endl;
    return 0;
}

---

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