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

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

2019-03-15

AtCoder AGC 001 A - BBQ Easy (200 点)

AtCoder AGC-A AtCoder200点 Greedy ソート最適化テク:自明な上界が最適解グルーピング(算数) グルーピングの最適化数列マッチング Greedyなマッチング最大スコアテーマにストーリー性のある面白い問題思わず解きたくなる興味深い良問ソート:条件を満たすまで大きい順に取っていく Greedy:条件を満たすまで大きい順に取っていく最適化問題

伝説の始まり

問題へのリンク

問題概要

$2N$ 個の整数 $L_1, L_2, \dots, L_{2N}$ が与えられる。

これらを $2$ 個ずつ $N$ 組作り、各組についての「小さい方の値」の総和を最大にしたい。

制約

$1 \le N \le 100$

考えたこと

小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまって損をする。

例えば、(3, 5, 98, 100) のとき、

(3 と 100)
(5 と 98)

みたいにしてしまうと、98 も 100 も消えて 3 + 5 = 8 となって大損である。このようなことを防ぐためには、小さいものは小さいもの同士、大きいものは大きいもの同士組んだ方がいい。

具体的には $2N$ 個の整数全体を小さい順にソートして ( $R_1, R_2, \dots, R_{2N}$ とする)、その順に 2 つ組を作って行くのが良い。

念のための証明 (本番はここまでしなくて良さそう)

厳密に証明しようと思ったら、「その答えより小さくは絶対にできない」ことを言えば良くて、一般に

$k$ 番目の組のスコアが $R_{2k-1}$ より小さくはできない

ということが言えるので、全体として

$R_1 + R_3 + \dots$

より小さくすることはできない。しかるにこれは「小さい順に 2 つ組を作る」という方法で達成できるので、これが最適解である。

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

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