cp-problems

都市めぐり

解説

\(N\) 個の都市を巡回順にして環状に並べたとき，コストのうち \((j - i)\) の部分は全て打ち消しあうため，無視してもよいです．

よって，\(1,\, 2,\, \dots,\, N\) の順列 \((A_i)\) のうち， \(A_1A_2 + A_2A_3 + \cdots + A_{N-1}A_N + A_NA_1\) が最小になるものを求めればよいということがわかります．

たとえば次の方法で上の式が最小になる順列を構築することができます．

\(\{1,N-1,3,N-3,5,\dots,4,N-2,2,N\}\)

また，\(O(1)\) で解けます．(参考:OEIS A110611)

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

signed main() {
    ll N;
    cin >> N;
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }
    ll num = 1;
    vector<ll> A, B;
    for (ll i = 0; i < N; i++) {
        // 1 を先頭に追加
        // ↓
        // N を後尾に追加
        // ↓
        // 2 を後尾に追加
        // ↓
        // N - 1 を先頭に追加
        // ↓
        // ⋮
        if (i % 2 == 0) {
            if (i % 4 == 0) {
                A.push_back(num);
            } else {
                B.push_back(num);
            }
            num = N - num + 1;
        } else {
            if (i % 4 == 1) {
                B.push_back(num);
            } else {
                A.push_back(num);
            }
            num = N - num + 2;
        }
    }
    reverse(B.begin(), B.end());
    A.insert(A.end(), B.begin(), B.end());
    ll res = 0;
    for (ll i = 0; i < N; i++) {
        res += A[i] * A[(i + 1) % N];
    }
    cout << res << endl;
}