C++で最大K個のペアを選択した際の最大コストを求める方法

問題の概要

ペア（組）からなる配列 A が与えられたとき、最大 K 個のペアを選択した場合のコストの最大値を求めることを考えます。ここで、選択したペア群のコストは次のように定義されます。

コスト =（選択したペアの第1要素の合計）×（選択したペアの中で第2要素の最小値）

例えば、(4, 8)、(10, 3)、(3, 6) の3つのペアを選んだ場合（K = 3）、コストは (4 + 10 + 3) × 3 = 51 となります。

入力例と出力例

次のような入力を考えてみましょう。

A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8), (12, 17)]、K = 4

このとき、出力は 2700 になります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• res := 0、sum := 0 として初期化します。
• N := 配列 A のサイズとします。
• ペアを格納する集合 my_set を定義します。
• 各ペアの第2要素に基づいて配列 A を昇順にソートします。
• i := N - 1 から始め、i ≥ 0 の間 i を1ずつ減らしながら以下を繰り返します。
  • (A[i] の第1要素, i) のペアを作成し、my_set に挿入します。
  • sum := sum + A[i] の第1要素 とします。
  • my_set のサイズが K を超えている間、次を繰り返します。
    • it := my_set の先頭要素
    • sum := sum − it の第1要素
    • my_set から it を削除します。
  • res := max(res, sum × A[i] の第2要素) とします。
• res を返します。

このアルゴリズムのポイントは、第2要素を降順に走査することで、「現在注目しているペアの第2要素が、選択中のペアの中で必ず最小値になる」という性質を利用できる点です。これにより、あとは第1要素の合計を最大化するだけでよくなります。そこで std::set を用いて常に第1要素が大きい上位 K 個だけを保持し、合計を効率的に更新しています。全体の計算量は O(N log N) です。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool compactor(const pair<int, int>& a, const pair<int, int>& b) {
    return (a.second < b.second);
}
int get_maximum_cost(vector<pair<int, int>> &A, int K){
    int res = 0, sum = 0;
    int N = A.size();
    set<pair<int, int>> my_set;
    sort(A.begin(), A.end(), compactor);
    for (int i = N - 1; i >= 0; --i) {
        my_set.insert(make_pair(A[i].first, i));
        sum += A[i].first;
        while (my_set.size() > K) {
            auto it = my_set.begin();
            sum -= it->first;
            my_set.erase(it);
        }
        res = max(res, sum * A[i].second);
    }
    return res;
}
int main() {
    vector<pair<int, int>> arr = {{15, 5}, {65, 25}, {35, 20}, {20, 5}, {35, 20}, {15, 18}, {3, 8}, {12, 17}};
    int K = 4;
    cout << get_maximum_cost(arr, K);
}

入力

{{15, 5}, {65, 25}, {35, 20}, {20, 5}, {35, 20}, {15, 18}, {3, 8}, {12, 17}}, 4

出力

2700