ferinの競プロ帳

競プロについてのメモ

2018-2019 ACM-ICPC, Asia Seoul Regional Contest C - Disks Arrangement

問題ページ
まず答えを 2 \sum a_i とする.ここから円盤を隣接させて被る分を引いていく.a_ia_j を隣接させるときに減少させられる幅は a_i+a_j-2\sqrt{a_ia_j} である.順列をうまく定めることでこの幅の和を最大化したい.グラフで表現すると n 頂点の完全グラフで,頂点 ij の間に a_i+a_j-2\sqrt{a_ia_j} の重みの辺を張ったグラフでハミルトンパスの長さの最大化を行えばよい.

a_i をソートしておくと辺の重み関数 w_{ij} = a_i+a_j-2\sqrt{a_ia_j} はsupnick(monge かつ 対称)である.重み関数がsupnickの場合,ハミルトン閉路の長さの最大化は (n, 2, n-2, 4, n-4, \ldots, 5, n-3, 3, n-1, 1) と順に訪れることで達成できる(らしい TSP, Max TSP and Supnick).今回求めたいのはハミルトンパスなのでハミルトン閉路のうち使わない辺が一つある.使わない辺について全探索すればよい.

辺の重みの行列がsupnickだとTSPが高速という知識,はたして今後使うことはあるのだろうか・・・

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    deque<ll> a(n);  
    REP(i, n) cin >> a[i];  
    sort(ALL(a));  
  
    vector<ll> v1, v2;  
    while(1) {  
        v1.push_back(a.back()); a.pop_back();  
        if(a.empty()) break;  
        v2.push_back(a[0]); a.pop_front();  
        if(a.empty()) break;  
        v1.push_back(a[0]); a.pop_front();  
        if(a.empty()) break;  
        v2.push_back(a.back()); a.pop_back();  
        if(a.empty()) break;  
    }  
    reverse(ALL(v2));  
    for(auto i: v2) v1.push_back(i);  
  
    // v1 の順に訪れていくとハミルトン閉路が最大になる  
    // 切る場所を全部試す  
    using R = long double;  
    R ans = INF;  
    REP(loop, n) {  
        R ret = v1[0] + v1[n-1];  
        FOR(i, 1, n) ret += 2 * sqrt(v1[i-1] * v1[i]);  
        chmin(ans, ret);  
        rotate(v1.begin(), v1.begin()+1, v1.end());  
    }  
    cout << fixed << setprecision(9) << ans << endl;  
  
    return 0;  
}  
``