AtCoder AGC 012 A - AtCoder Group Contest (茶色, 300 点)

これほとんど

drken1215.hatenablog.com

と同じ問題！！！

問題へのリンク

問題概要

を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。

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

制約

• 

考えたこと

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 個ずつ切って順にチームに入れて行って、残った下位 個をテキトーに入れていく方法になる。これが最適になることの証明は

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;
}