Helvetic Coding Contest 2018 E2. Guard Duty (medium)
解説
わからなかったので上位陣のコードから解法を得た.
とりあえずソートして隣接項の差を作ると,以下の問題になる.
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; }
感想
これめっちゃ頭いい….思いつけたら気持ちいいだろうなあ.
賢い人は自明とかいうんだろうな….