Helvetic Coding Contest 2018 E2. Guard Duty (medium)

問題文

http://codeforces.com/contest/958/problem/E2

解説

わからなかったので上位陣のコードから解法を得た．
とりあえずソートして隣接項の差を作ると，以下の問題になる．

n - 1 要素からなる数列から，k 個えらんでその和を最小化せよ．ただし，隣接2要素を取ってはならない．

基本は貪欲的に取っていく．つまりコストが小さい方から順に取る．
ここで，取ったやつの隣をどう扱うか考えるのだが，頭のいいやり方がある．
それは，今現在選んだ要素と，それに隣接している要素の集合の集合（集合の集合という表現であっている）を1つの整数値にまとめて set で管理するというものである．
たとえば，初期状態から考えると，それは n - 1 要素からなる集合となる（各集合は1つの要素からなる）．
この時 a[i] を選択したとすると，集合から a[i - 1], a[i], a[i + 1] を削除して新たに a[i - 1] + a[i + 1] - a[i] を追加する．そして，仮に次に a[i - 1] + a[i + 1] - a[i] の要素を選択するとするなら，それは a[i - 1] と a[i + 1] を選択したのを同じ状態になる．
したがって，この貪欲アルゴリズムを k 回行えば，最適解が求まる．

ソースコード

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

using ll = long long;

constexpr ll inf = 1e18;

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(begin(a), end(a));

    set<pair<ll, ll>> index_value, value_index;
    for(int i = 0; i + 1 < n; ++i) {
        index_value.emplace(i, a[i + 1] - a[i]);
        value_index.emplace(a[i + 1] - a[i], i);
    }
    index_value.emplace(-1, inf);
    index_value.emplace(n, inf);
    value_index.emplace(inf, -1);
    value_index.emplace(inf, n);

    ll res = 0;
    for(int lp = 0; lp < k; ++lp) {
        int v, l, r;
        ll val, lval, rval;
        tie(val, v) = *begin(value_index);
        auto it = index_value.lower_bound(make_pair(v, val));
        tie(l, lval) = *prev(it);
        tie(r, rval) = *next(it);

        index_value.erase(make_pair(v, val));
        index_value.erase(make_pair(l, lval));
        index_value.erase(make_pair(r, rval));
        value_index.erase(make_pair(val, v));
        value_index.erase(make_pair(lval, l));
        value_index.erase(make_pair(rval, r));
        index_value.emplace(v, lval + rval - val);
        value_index.emplace(lval + rval - val, v);
        res += val;
    }

    cout << res << endl;
}

感想

これめっちゃ頭いい…．思いつけたら気持ちいいだろうなあ．
賢い人は自明とかいうんだろうな…．