2014 Yandex.Algorithm Elimination Stage, Round1 B - Adjusting Ducks

問題文

問題概要

n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える．
この操作によって，数列に含まれる値として，単独で存在するものがないようにしたい．最小のコストはいくらかかかるか？

・制約
1 <= n <= 10^5
1 <= a_i <= 10^8

解法

基本的には値の近い2つの数字をペアにしていけば良さそうである．
よって，最初にソートして以下の dp をした．

dp[i][j] := i 番目の要素まで見て，その要素が直前の要素に変えられたか，あるいは直前の値を今見ている値に変えたかとしたときの最小コスト．

今見ている要素に直前の値を合わせる時，そのさらに前の（つまり2個前）要素は，今見ている要素に合わせるのは明らかに不利である．なぜなら，その場合は直前の要素に今の値を合わせたほうがコストが小さく済むからである．
したがって，この場合は2つ前の要素は，今見ている要素とは無関係に考えてよい．

次に，今見ている要素を直前の値に合わせるときは，同じような理由で2つ前の値は直前の値に変えられていると考えて良い．
この遷移のやり方だと，今見ている値を直前の値に合わせて，かつ2つ前の値をその前の値に合わせるようなものを考えていないようだが，実は問題ない．なぜなら，これは直前の値を今見ている値に合わせたのと同じだからであり，これは先程の遷移に含まれているからである．

以上で O(N) でこの問題をとくことができる．

ソースコード

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

using ll = long long;

template <typename T> constexpr T inf;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(begin(a), end(a));
    vector<vector<ll>> dp(n + 1, vector<ll>(2, inf<ll>));
    dp[1][0] = dp[1][1] = abs(a[0] - a[1]);
    for(int i = 2; i < n; ++i) {
        dp[i][0] = dp[i - 1][1] + a[i] - a[i - 1];
        dp[i][1] = min(dp[i - 2][1], dp[i - 2][0]) + a[i] - a[i - 1];
    }
    cout << min(dp[n - 1][0], dp[n - 1][1]) << endl;
}

感想

変な dp をしてしまったが，もっとわかりやすいのがありそう．うーん．