#782937 (C++17) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: qLethon
• 提出日時: 2022-07-30 15:02:49
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 503 ms / 1,000 ms
• コード長: 10,227 bytes
• コンパイル時間: 2,864 ms
• 実行使用メモリ: 3,848 KB
• スコア: 4,769,099
• 最終ジャッジ日時: 2022-07-30 15:03:10
• 合計ジャッジ時間: 20,205 ms
• ジャッジサーバーID （参考情報）: judge10 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	502 ms; 3,684 KB
testcase_01	AC	502 ms; 3,784 KB
testcase_02	AC	502 ms; 3,808 KB
testcase_03	AC	502 ms; 3,832 KB
testcase_04	AC	502 ms; 3,736 KB
testcase_05	AC	502 ms; 3,684 KB
testcase_06	AC	502 ms; 3,836 KB
testcase_07	AC	503 ms; 3,688 KB
testcase_08	AC	503 ms; 3,752 KB
testcase_09	AC	502 ms; 3,840 KB
testcase_10	AC	502 ms; 3,848 KB
testcase_11	AC	502 ms; 3,684 KB
testcase_12	AC	502 ms; 3,688 KB
testcase_13	AC	503 ms; 3,808 KB
testcase_14	AC	502 ms; 3,752 KB
testcase_15	AC	502 ms; 3,780 KB
testcase_16	AC	502 ms; 3,788 KB
testcase_17	AC	503 ms; 3,752 KB
testcase_18	AC	502 ms; 3,832 KB
testcase_19	AC	503 ms; 3,844 KB
testcase_20	AC	502 ms; 3,748 KB
testcase_21	AC	502 ms; 3,844 KB
testcase_22	AC	503 ms; 3,808 KB
testcase_23	AC	502 ms; 3,812 KB
testcase_24	AC	502 ms; 3,784 KB
testcase_25	AC	502 ms; 3,736 KB
testcase_26	AC	502 ms; 3,784 KB
testcase_27	AC	502 ms; 3,832 KB
testcase_28	AC	502 ms; 3,736 KB
testcase_29	AC	503 ms; 3,732 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;

u_int64_t seed = 91;
u_int64_t xor_shift(){
    seed ^= seed << 1;
    seed ^= seed >> 3;
    seed ^= seed << 10;
    return seed;
}

class Time{
    public:
    chrono::system_clock::time_point start_time;
    Time(){
        start_time = now();
    }

    chrono::system_clock::time_point now(){
        return chrono::system_clock::now();
    }

    int elapsed(){
        auto cur = chrono::system_clock::now();
        return chrono::duration_cast<chrono::milliseconds>(cur - start_time).count();
    }
};

template <class T>
class TSP{
    vector<vector<T>> D;
    vector<int> ans, A, v_to_cycle;
    vector<vector<int>> nearest;
    int n;
    T INF;
    public:
    TSP (vector<vector<T>> D, T INF): D(D), n(D.size()), INF(INF){
        ans.resize(n);
        iota(ans.begin(), ans.end(), 0);
        v_to_cycle.resize(n);
        iota(v_to_cycle.begin(), v_to_cycle.end(), 0);
        A.resize(n);
        iota(A.begin(), A.end(), 0);

        nearest.assign(n, vector<int>(n));
        for (int i = 0; i < n; i++){
            vector<pair<T, int>> B(n);
            for (int j = 0; j < n; j++)
                B[j] = {D[i][j], j};
            sort(B.begin(), B.end());
            for (int j = 0; j < n; j++)
                nearest[i][j] = B[j].second;
        }
    };

    vector<int> solve_perm(){
        vector<int> P(n);
        iota(P.begin(), P.end(), 0);

        T best_score = INF;
        vector<int> best = P;
        do {
            T s = calc_score(P);
            if (s < best_score){
                best = P;
                best_score = s;
            }
        } while (next_permutation(P.begin(), P.end()));
    
        return best;
    }
    
    vector<int> solve(int time_limit){
        if (n < 10)
            return solve_perm();

        Time time;

        // // initial 2-opt
        // while (true){
        //     bool updated = false;
        //     for (int t1 = 0; t1 < n; t1++){
        //         int t2 = (t1 + 1) % n;
        //         for (const auto &v: nearest[ans[t2]]){
        //             int t3 = v_to_cycle[v];
        //             if (dist(t1, t2) <= dist(t2, t3))
        //                 break;
        //             int t4 = (t3 - 1 + n) % n;
        //             int i, j;
        //             if (t2 <= t4)
        //                 tie(i, j) = {t2, t4};
        //             else
        //                 tie(i, j) = {t3, t1};
                    
        //             const auto d = calc_two_opt_score(i, j);
        //             if (d < 0){
        //                 two_opt_swap(i, j);
        //                 updated = true;
        //             }
        //         }
        //     }
        //     if (!updated)
        //         break;
        // }

        // kick (double bridge + 2-opt)
        auto best = ans;
        auto best_v_to_cycle = v_to_cycle;
        T score = calc_score(ans);
        int loop = 0;

        while (time.elapsed() < time_limit){
            loop++;
            ans = best;
            v_to_cycle = best_v_to_cycle;

            // kick
            T diff = 0;
            {
            auto chosen = choose_k(4);
            sort(chosen.begin(), chosen.end());
            diff = calc_double_bridge(chosen[0], chosen[1], chosen[2], chosen[3]);
            double_birdge(chosen[0], chosen[1], chosen[2], chosen[3]);
            }

            // // random 2-opt
            // for (int i = 0; i < 6; i++){
            //     const int a = xor_shift() % n;
            //     const int b = xor_shift() % n;
            //     diff += calc_two_opt_score(a, b);
            //     two_opt_swap(a, b);
            // }
            
            vector<int> Q(n);
            iota(Q.begin(), Q.end(), 0);

            // local optimization
            while (true){
                bool updated = false;
                vector<int> NQ;
                for (auto u: Q){
                    int t1 = v_to_cycle[u];
                    int t2 = (t1 + 1) % n;
                    for (const auto &v: nearest[ans[t2]]){
                        int t3 = v_to_cycle[v];
                        if (dist(t1, t2) <= dist(t2, t3))
                            break;
                        int t4 = (t3 - 1 + n) % n;
                        int i, j;
                        if (t2 <= t4)
                            tie(i, j) = {t2, t4};
                        else
                            tie(i, j) = {t3, t1};
                        
                        const auto d = calc_two_opt_score(i, j);
                        if (d < 0){
                            NQ.push_back(ans[(t1 - 1 + n) % n]);
                            NQ.push_back(ans[t1]);
                            NQ.push_back(ans[t2]);
                            NQ.push_back(ans[(t2 + 1) % n]);
                            NQ.push_back(ans[(t4 - 1 + n) % n]);
                            NQ.push_back(ans[t3]);
                            NQ.push_back(ans[t4]);
                            NQ.push_back(ans[(t3 + 1) % n]);
                            two_opt_swap(i, j);
                            diff += d;
                            updated = true;
                            break;
                        }
                    }
                }
                if (!updated)
                    break;
                Q = NQ;
                sort(Q.begin(), Q.end());
                Q.erase(unique(Q.begin(), Q.end()), Q.end());
            }

            if (diff < 0){
                best = ans;
                best_v_to_cycle = v_to_cycle;
                score += diff;
                cerr << score << endl;
            }
        }

        cerr << "loop: " << loop << endl;
        // cerr << score << endl;
        return best;
    }

    T dist(int i, int j){
        // こっちに%n押し付けたいだろ
        if (i < 0)
            i += n;
        if (i >= n)
            i -= n;
        if (j < 0)
            j += n;
        if (j >= n)
            j -= n;
        return D[ans[i]][ans[j]];
    }

    T dist(int i, int j, const vector<int> &ans){
        return D[ans[i]][ans[j]];
    }

    T calc_score(const vector<int> &ans){
        T res = 0;
        assert(ans.size() > 0);
        for (int i = 0; i < ans.size() - 1; i++)
            res += dist(i, i + 1, ans);
        res += dist(ans.size() - 1, 0, ans);
        return res;
    }

    T calc_two_opt_score(int i, int j){
        T res = 0;
        if (i > j)
            swap(i, j);
        if (i == 0 and j == n - 1)
            return 0;

        res += dist((i - 1 + n) % n, j) - dist((i - 1 + n) % n, i);
        res += dist(i, (j + 1) % n) - dist(j, (j + 1) % n);
        
        return res;
    }

    void two_opt_swap(int i, int j){
        if (i > j)
            swap(i, j);
        reverse(ans.begin() + i, ans.begin() + j + 1);
        for (int a = i; a <= j; a++)
            v_to_cycle[ans[a]] = a;
    }

    T three_opt_swap(int i, int j, int k){
        assert(i < j and j < k);
        array<T, 5> d;

        i--; j--; k--;  // バカ

        d[0] = dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1);
        d[1] = dist(i, j) + dist(i + 1, j + 1) + dist(k, k + 1);
        d[2] = dist(i, i + 1) + dist(j, k) + dist(j + 1, k + 1);
        d[3] = dist(i, j + 1) + dist(k, i + 1) + dist(j, k + 1);
        d[4] = dist(k + 1, i + 1) + dist(j, j + 1) + dist(k, i);

        i++; j++; k++;

        if (d[0] > d[1]){
            reverse(ans.begin() + i, ans.begin() + j);
            return -d[0] + d[1];
        } else if (d[0] > d[2]){
            reverse(ans.begin() + j, ans.begin() + k);
            return -d[0] + d[2];
        } else if (d[0] > d[4]){
            reverse(ans.begin() + i, ans.begin() + k);
            return -d[0] + d[4];
        } else if (d[0] > d[3]){
            vector<int> tmp(k - i);
            copy(ans.begin() + j, ans.begin() + k, tmp.begin());
            copy(ans.begin() + i, ans.begin() + j, tmp.begin() + k - j);
            copy(tmp.begin(), tmp.end(), ans.begin() + i);
            return -d[0] + d[3];
        }
        return 0;
    }

    T calc_double_bridge(int i, int j, int k, int l){
        assert(i < j and j < k and k < l);
        T res = 0;
        res -= dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1) + dist(l, (l + 1) % n);
        res += dist(i, k + 1) + dist(j, (l + 1) % n) + dist(k, i + 1) + dist(l, j + 1);

        return res;
    }

    void double_birdge(int i, int j, int k, int l){
        assert(i < j and j < k and k < l);
        assert(l < n);
        vector<int> res(n);
        copy(ans.begin(), ans.begin() + i + 1, res.begin());
        copy(ans.begin() + k + 1, ans.begin() + l + 1, res.begin() + i + 1);
        copy(ans.begin() + j + 1, ans.begin() + k + 1, res.begin() + i + l - k + 1);
        copy(ans.begin() + i + 1, ans.begin() + j + 1, res.begin() + i + l - j + 1);
        copy(ans.begin() + l + 1, ans.end(), res.begin() + l + 1);
        ans = res;

        for (int a = 0; a < n; a++)
            v_to_cycle[ans[a]] = a;
    }

    vector<int> choose_k(int k){
        const int m = A.size();
        assert(k <= m);
        vector<int> res(k);
        for (int i = 0; i < k; i++){
            int r = i + xor_shift() % (m - i);
            swap(A[i], A[r]);
            res[i] = A[i];
        }

        return res;
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> A(n), B(n);
    for (int i = 0; i < n; i++)
        cin >> A[i] >> B[i];

    constexpr int alpha = 5;
    vector<vector<int64_t>> D(n, vector<int64_t>(n));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            D[i][j] = (A[i] - A[j]) * (A[i] - A[j]) + (B[i] - B[j]) * (B[i] - B[j]) * alpha * alpha;
        }
    }

    TSP tsp(D, int64_t(1e15));

    auto ans = tsp.solve(500);

    cerr << tsp.calc_score(ans) << endl;

    for (int i = 0; i < m; i++)
        cout << "0 0" << endl;
    
    for (int i = 0; i < n; i++){
        if (ans[i] == 0)
            rotate(ans.begin(), ans.begin() + i, ans.end());
    }
    assert(ans[0] == 0);

    cout << n + 1 << endl;
    for (const auto &a: ans)
        cout << "1 " << a + 1 << endl;
    cout << "1 1" << endl;

}