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

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	shibh308
提出日時	2022-07-30 17:02:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	934 ms / 1,000 ms
コード長	13,491 bytes
コンパイル時間	2,746 ms
実行使用メモリ	6,952 KB
スコア	8,893,705
最終ジャッジ日時	2022-07-30 17:02:44
合計ジャッジ時間	33,221 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	933 ms 4,904 KB
testcase_01	AC	906 ms 4,900 KB
testcase_02	AC	930 ms 4,904 KB
testcase_03	AC	934 ms 4,908 KB
testcase_04	AC	929 ms 4,900 KB
testcase_05	AC	932 ms 6,948 KB
testcase_06	AC	907 ms 4,900 KB
testcase_07	AC	929 ms 4,904 KB
testcase_08	AC	906 ms 6,952 KB
testcase_09	AC	930 ms 6,948 KB
testcase_10	AC	906 ms 4,900 KB
testcase_11	AC	907 ms 4,904 KB
testcase_12	AC	931 ms 4,904 KB
testcase_13	AC	906 ms 6,952 KB
testcase_14	AC	930 ms 4,900 KB
testcase_15	AC	907 ms 6,948 KB
testcase_16	AC	913 ms 4,908 KB
testcase_17	AC	931 ms 4,900 KB
testcase_18	AC	906 ms 4,908 KB
testcase_19	AC	930 ms 4,900 KB
testcase_20	AC	904 ms 4,904 KB
testcase_21	AC	918 ms 4,904 KB
testcase_22	AC	920 ms 4,900 KB
testcase_23	AC	905 ms 4,904 KB
testcase_24	AC	931 ms 4,904 KB
testcase_25	AC	907 ms 6,948 KB
testcase_26	AC	929 ms 4,904 KB
testcase_27	AC	907 ms 6,948 KB
testcase_28	AC	910 ms 6,948 KB
testcase_29	AC	930 ms 4,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18);

template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


uint32_t rnd(){
    static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 0;
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w;
}

double rnd_double(){
    return 1.0 * rnd() / numeric_limits<uint32_t>::max();
}

// #define OPTIMIZE

namespace params{
void load_params(){
    ifstream ifs("../params.txt");
    assert(ifs.is_open());
}
}


// doc: https://shibh308.github.io/library/library/lib/functions/tsp.cpp.html
template<typename T>
vector<int> tsp(int n, vector<int> init, vector<vector<T>> dist, int iter_num){
    // 始点=終点のTSP n <= 2 とかでバグりそうなので注意
    vector<int> v = init;
    vector<int> inv(n);
    T now_dist = 0;
    for(int i = 0; i < n; ++i){
        inv[v[i]] = i;
        now_dist += dist[v[i]][v[(i + 1) % n]];
    }
    // 前計算
    vector<vector<pair<T,int>>> near_vertexes(n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            near_vertexes[i].emplace_back(dist[i][j], j);
        }
        sort(near_vertexes[i].begin(), near_vertexes[i].end());
    }

    auto dist_check = [&](){
        auto di = dist[0][0];
        for(int i = 0; i < n; ++i){
            di += dist[v[i]][v[(i + 1) % n]];
        }
        assert(abs(now_dist - di) <= 1e-6);
    };

    auto update = [&](int i1, int i3){
        int i2 = (i1 + 1) % n;
        int i4 = (i3 + 1) % n;

        if(i1 == i3 || i2 == i3 || i1 == i4 || i2 == i4)
            return false;
        if(dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]] <= dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]])
            return false;

        auto improve = (dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]]) - (dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]]);
        now_dist -= improve;

        int d1 = (i2 < i3 ? i3 - i2 : i3 + n - i2);
        int d2 = (i4 < i1 ? i1 - i4 : i1 + n - i4);
        if(d1 >= d2){
            swap(i1, i3);
            swap(i2, i4);
        }

        int st = i2;
        int en = i2 < i3 ? i3 : i3 + n;
        while(st < en){
            inv[v[en % n]] = st % n;
            inv[v[st % n]] = en % n;
            swap(v[st % n], v[en % n]);
            ++st, --en;
        }
        // バグが怖い時用
        // dist_check();

        return true;
    };

    auto neighbors_search = [&](){
        for(int i = 0; i < n; ++i){
            int idx1 = i;
            int idx2 = (i + 1) % n;
            int v1 = v[idx1];
            int v2 = v[idx2];
            for(auto [d, v3] : near_vertexes[v1]){
                if(v3 == v2)
                    break;
                int idx3 = inv[v3];
                if(update(idx1, idx3)){
                    return true;
                }
            }
            for(auto [d, v4] : near_vertexes[v2]){
                if(v4 == v1)
                    break;
                int idx3 = (inv[v4] + n - 1) % n;
                if(update(idx1, idx3)){
                    return true;
                }
            }
        }
        return false;
    };
    auto double_bridge = [&](){
        vector<uint32_t> r{rnd() % n, rnd() % n, rnd() % n, rnd() % n};
        sort(r.begin(), r.end());
        if(r[0] == r[1] || r[1] == r[2] || r[2] == r[3]){
            return true;
        }
        // (r[3] + 1, r[0]) => (r[2] + 1, r[3]) => (r[1] + 1, r[2]) => (r[0] + 1, r[1])

        auto diff = dist[0][0];
        diff -= dist[v[r[0]]][v[r[0] + 1]];
        diff -= dist[v[r[1]]][v[r[1] + 1]];
        diff -= dist[v[r[2]]][v[r[2] + 1]];
        diff -= dist[v[r[3]]][v[(r[3] + 1) % n]];
        diff += dist[v[r[0]]][v[r[2] + 1]];
        diff += dist[v[r[3]]][v[r[1] + 1]];
        diff += dist[v[r[2]]][v[r[0] + 1]];
        diff += dist[v[r[1]]][v[(r[3] + 1) % n]];
        now_dist += diff;
        vector<int> nex;
        nex.reserve(n);
        for(int i = r[3] + 1; i < n; ++i)
            nex.emplace_back(v[i]);
        for(int i = 0; i <= r[0]; ++i)
            nex.emplace_back(v[i]);
        for(int i = r[2] + 1; i <= r[3]; ++i)
            nex.emplace_back(v[i]);
        for(int i = r[1] + 1; i <= r[2]; ++i)
            nex.emplace_back(v[i]);
        for(int i = r[0] + 1; i <= r[1]; ++i)
            nex.emplace_back(v[i]);
        v = move(nex);
        return false;
    };

    auto best = make_pair(now_dist, v);
    for(int i = 0; i < iter_num; ++i){
        if(i){
            while(double_bridge());
        }
        while(neighbors_search());
        if(!chmin(best, make_pair(now_dist, v))){
            tie(now_dist, v) = best;
        }
    }
    for(int i = 0; i < n; ++i){
        if(v[i] == 0){
            vector<int> res;
            for(int j = 0; j < n; ++j){
                res.emplace_back(v[(i + j) % n]);
            }
            return res;
        }
    }
    // return now_dist;
    return v;
}


constexpr int n = 100;
constexpr int m = 8;
constexpr int alpha = 5;
array<i64, n> ax, ay;

void read_file(istream& ifs){
    int a;
    ifs >> a >> a;
    // TODO: input
    for(int i = 0; i < n; ++i){
        ifs >> ax[i] >> ay[i];
    }
}

clock_t st;

void solve(){
    vector<vector<i64>> a_dist(n, vector<i64>(n));
    vector<i64> bx(n), by(n);

    auto raw_dis = [&](auto p1, auto q1, auto p2, auto q2){
        i64 dx = (p1 == 0 ? ax[q1] : bx[q1]) - (p2 == 0 ? ax[q2] : bx[q2]);
        i64 dy = (p1 == 0 ? ay[q1] : by[q1]) - (p2 == 0 ? ay[q2] : by[q2]);
        return dx * dx + dy * dy;
    };
    auto dis = [&](auto p1, auto q1, auto p2, auto q2){
        int alp = 1;
        alp *= (p1 == 0 ? 5 : 1);
        alp *= (p2 == 0 ? 5 : 1);
        return raw_dis(p1, q1, p2, q2) * alp;
    };

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            a_dist[i][j] = dis(0, i, 0, j);
        }
    }

    vector<vector<int>> idxes_x(1001);
    for(int i = 0; i < n; ++i){
        idxes_x[ax[i]].emplace_back(i);
    }

    /*
    vector<vector<i64>> points(1001, vector<i64>(1001, 0));
    for(int i = 0; i < n; ++i){
        for(int x = max(0LL, ax[i] - 300); x < min(ax[i] + 300, 100LL); ++x){
            for(int y = max(0LL, ay[i] - 300); y < min(ay[i] + 300, 100LL); ++y){
                int dx = x - ax[i];
                int dy = y - ay[i];
                if(dx * dx + dy * dy <= 100 * 100){
                    ++points[x][y];
                }
            }
        }
    }
    */

    bx = {200, 400, 600, 800};
    by = {333, 333, 333, 333, 666, 666, 666, 666};
    for(int i = 0; i < 8; ++i){
        bx[i] = bx[i % 4];
    }
    /*
    for(int j = 0; j < 8; ++j){
        bool fl = false;
        while(!fl && points[bx[j]][by[j]] <= 10){
            bx[j] = 100 + rnd() % 800;
            by[j] = 100 + rnd() % 800;
            fl = true;
            for(int i = 0; i < j; ++i){
                int dx = bx[i] - bx[j];
                int dy = by[i] - by[j];
                if(sqrt(dx * dx + dy * dy) <= 300){
                    fl = false;
                    break;
                }
            }
        }
    }
     */

    vector<int> v(100);
    iota(v.begin(), v.end(), 0);
    auto res = tsp(100, v, a_dist, 100);
    res.emplace_back(0);

    auto calc_ans = [&](){
        vector<pair<int,int>> ans;
        ans.emplace_back(0, 0);
        i64 ds = 0;
        for(int i = 0; i < n; ++i){
            i64 d = dis(0, res[i], 0, res[i + 1]);
            pair<i64,int> pp(d, -1);
            for(int j = 0; j < m; ++j){
                i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]);
                chmin(pp, make_pair(d2, j));
            }
            ds += pp.first;
            if(pp.second != -1){
                ans.emplace_back(1, pp.second);
            }
            ans.emplace_back(0, res[i + 1]);
        }
        return make_pair(ans, ds);
    };
    auto calc_ans_light = [&](){
        i64 ds = 0;
        for(int i = 0; i < n; ++i){
            i64 d = dis(0, res[i], 0, res[i + 1]);
            pair<i64,int> pp(d, -1);
            for(int j = 0; j < m; ++j){
                i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]);
                chmin(pp, make_pair(d2, j));
            }
            ds += pp.first;
        }
        return ds;
    };

    auto calc_sc = [&](i64 dist){
        return round(1000000000 / (1000 + sqrt(dist)));
    };


    auto best = calc_ans_light();
    auto best_b = make_pair(bx, by);
    bool fl = true;
    int itr = 0;
    constexpr double start_temp = 1;//100000;
    constexpr double end_temp = 1e-6;
    constexpr double end_time = 0.9;
    double per = 0.0;
    bool upd = true;
    while(fl){
        // cout << per << endl;
        for(int _ = 0; _ < 100; ++_){
            double new_per = double(clock() - st) / CLOCKS_PER_SEC / end_time;
            if(new_per >= 1.0){
                fl = false;
                break;
            }

            if(itr && itr % 3000 == 0 && upd){
                // if(per < 0.3 && new_per >= 0.3){
                // cout << new_per << ": " << "TSP    ";
                vector<vector<i64>> dist(n, vector<i64>(n));
                for(int i = 0; i < n; ++i){
                    for(int j = 0; j < n; ++j){
                        dist[i][j] = dis(0, i, 0, j);
                        for(int k = 0; k < 8; ++k){
                            chmin(dist[i][j], dis(0, i, 1, k) + dis(1, k, 0, j));
                        }
                    }
                }
                res = tsp(n, res, dist, 50);
                res.emplace_back(0);
                // cout << best << " -> ";
                best = calc_ans_light();
                // cout << best << endl;
                upd = false;
            }

            // per = new_per;

            ++itr;
            int idx = rnd() & 7;
            int px = bx[idx];
            int py = by[idx];
            int dx, dy;
            int ty = 0;
            if(rnd() % 4){
                if(new_per >= 0.5){
                    dx = rnd() % 12 - 6;
                    dy = rnd() % 12 - 6;
                }
                else if(new_per >= 0.2){
                    dx = rnd() % 50 - 25;
                    dy = rnd() % 50 - 25;
                }
                else if(new_per >= 0.15){
                    dx = rnd() % 100 - 50;
                    dy = rnd() % 100 - 50;
                }
                else{
                    dx = rnd() % 300 - 150;
                    dy = rnd() % 300 - 150;
                }
                if(dx == 0 && dy == 0){
                    continue;
                }
                bx[idx] += dx;
                by[idx] += dy;
            }
            else if(rnd() % 10 == 0){
                int po = 0;
                for(int i = 0; i < n; ++i){
                    if(dis(0, res[i], 0, res[i + 1]) > dis(0, res[i], 1, idx) + dis(1, idx, 0, res[i + 1])){
                        po = i;
                        break;
                    }
                }
                double dp = 0.5 + 0.5 * rnd_double();
                int nx = ax[res[po]] + dp * (px - ax[res[po]]);
                int ny = ay[res[po]] + dp * (py - ay[res[po]]);
                bx[idx] = nx;
                by[idx] = ny;
                ty = 1;
            }
            else{
                dx = rnd() % 600 - 300;
                dy = rnd() % 600 - 300;
                bx[idx] += dx;
                by[idx] += dy;
                ty = 2;
            }
            auto now = calc_ans_light();
            auto diff = best - now;
            /*
            if(ty == 1){
                cout << px << " " << py << " " << bx[idx] << " " << by[idx] << endl;
                cout << diff << endl;
            }
             */
            // cout << diff << " " << temp << " : " << exp(diff / temp) << endl;
            // if(exp(diff / temp) >= rnd_double()){
            if(diff >= 0){
                /*
                if(ty != 1){
                    cout << new_per << ": " << dx << " " << dy << "     " << best << " -> " << now << endl;
                }
                else{
                    cout << new_per << ": mov     " << best << " -> " << now << endl;
                }
                 */
                // cout << points[bx[idx]][by[idx]] << endl;
                best = now;
                // cout << calc_sc(best) << " " << ty << endl;
                best_b = make_pair(bx, by);
                upd = true;
            }
            else{
                bx[idx] = px;
                by[idx] = py;
            }
        }
    }
    // cout << itr << endl;


    tie(bx, by) = best_b;
    auto ans = calc_ans().first;

#ifdef HAND
    cout << calc_sc(best) << endl;
    cout << itr << endl;
#else
    for(int i = 0; i < m; ++i){
        cout << bx[i] << " " << by[i] << endl;
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); ++i){
        cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
    }
#endif
}

signed main(){

    st = clock();

#ifdef OPTIMIZE
    params::load_params();
#endif

#ifndef HAND
    read_file(cin);
#else
    ifstream ifs("./tools/in/0000.txt");
    assert(ifs.is_open());
    read_file(ifs);
#endif

    solve();

}

yukicoder

結果

テストケース

ソースコード