けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 012 A - AtCoder Group Contest (300 点)

これほとんど

drken1215.hatenablog.com

と同じ問題!!!

問題へのリンク

問題概要

 N を整数として  3N 個の整数  a_{1}, \dots, a_{3N} が与えられる。これらを 3 個ずつ  N 組のペアを作る。

ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを最大にせよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

AGC 001 - BBQ Easy の問題は、この問題で「3 つ組」ではなく「2 つ組」に関する問題だった。

それに比べると「3 つ組」になった分、少し難しくなる。パッと思いつく方法として、大きい順に並べて

12, 10, 9, 8, 6, 5, 4, 4, 2

として、これを順に 3 個ずつ区切って行く方法が思い浮かびそうになる。つまり

12, 10, 9
8, 6, 5
4, 4, 2

として 10 + 6 + 4 = 20 になる。しかしこれは嘘で、例えば一番目の「12, 10, 9」の 9 をこんなところで消費してはもったいない。真の最適解は、

12, 10, ?
9, 8, ?
6, 5 ?

のように、大きい方からとりあえず 2 個ずつ切って順にチームに入れて行って、残った下位  N 個をテキトーに入れていく方法になる。これが最適になることの証明は

drken1215.hatenablog.com

で書いたものとまったく同じようにしてできる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N*3);
    for (int i = 0; i < N*3; ++i) cin >> A[i];
    sort(A.begin(), A.end(), greater<long long>());
    long long res = 0;
    for (int i = 1, j = 0; j < N; i += 2, ++j) res += A[i];
    cout << res << endl;
}