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

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	tmikada
提出日時	2023-04-30 16:12:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	998 ms / 1,000 ms
コード長	15,776 bytes
コンパイル時間	3,108 ms
コンパイル使用メモリ	232,540 KB
実行使用メモリ	4,372 KB
スコア	8,091,880
最終ジャッジ日時	2023-04-30 16:12:49
合計ジャッジ時間	35,169 ms
ジャッジサーバーID （参考情報）	judge16 / judge14
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	975 ms 4,372 KB
testcase_01	AC	947 ms 4,372 KB
testcase_02	AC	972 ms 4,372 KB
testcase_03	AC	949 ms 4,368 KB
testcase_04	AC	972 ms 4,368 KB
testcase_05	AC	998 ms 4,372 KB
testcase_06	AC	948 ms 4,368 KB
testcase_07	AC	972 ms 4,368 KB
testcase_08	AC	949 ms 4,368 KB
testcase_09	AC	974 ms 4,372 KB
testcase_10	AC	973 ms 4,372 KB
testcase_11	AC	948 ms 4,368 KB
testcase_12	AC	963 ms 4,368 KB
testcase_13	AC	949 ms 4,368 KB
testcase_14	AC	973 ms 4,368 KB
testcase_15	AC	973 ms 4,368 KB
testcase_16	AC	947 ms 4,368 KB
testcase_17	AC	973 ms 4,368 KB
testcase_18	AC	948 ms 4,368 KB
testcase_19	AC	975 ms 4,368 KB
testcase_20	AC	953 ms 4,368 KB
testcase_21	AC	949 ms 4,368 KB
testcase_22	AC	950 ms 4,368 KB
testcase_23	AC	973 ms 4,368 KB
testcase_24	AC	978 ms 4,372 KB
testcase_25	AC	951 ms 4,372 KB
testcase_26	AC	973 ms 4,372 KB
testcase_27	AC	948 ms 4,372 KB
testcase_28	AC	974 ms 4,368 KB
testcase_29	AC	972 ms 4,368 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

using namespace std;
using ll=long long;

// Start 2023.04.23 21:00 
// End   
// Time  min

// MTK005

constexpr ll TYPE_PLANET = 1;
constexpr ll TYPE_STATION = 2;
constexpr ll ALPHA = 5;
constexpr ll INF = (1LL << 60);

ll START_TIME = 0;

struct Pos {
    int x,y;
    ll type;
    Pos(int x, int y, ll type) : x(x), y(y), type(type) {}
};
std::ostream& operator<<(std::ostream& os, const Pos& pos) {
    std::ostringstream oss;
    oss << "(" << pos.x << ", " << pos.y << "), " << pos.type << "";
    os << oss.str();
    return os;
}

struct Solver {
	int N = 0;
	int M = 0;
    vector<Pos> points;

    Solver(int n, int m, vector<Pos>& points) : N(n),M(m),points(points) {}

    void test() {
        debug(N,M,points);
    }

    void solve() {

        // 貪欲法
        set_station();
        // debug(points);

        // 全点間エネルギーを計算
        vector<vector<int>> distances = calc_distance();

        // 惑星1からスタートする
        // 一番近い惑星＋宇宙ステーションを選び続ける
        vector<int> route = greedy(distances);
        debug(route);  

        double limit1 = 0.1;
        double limit2 = 0.93-limit1;

        // 宇宙ステーションを１つ選んでずらす
        {
            double current_score = calc_score(route);
            int ti = clock();
            int TIMELIMIT = limit1 * CLOCKS_PER_SEC;
            int cnt = 1;
            int kaizen = 0;
            int random = 0;
            while(clock() - ti < TIMELIMIT) {
                // debug(clock()-ti,__LINE__,cnt);
                cnt++;
                // ずらす宇宙ステーションをランダムに選ぶ
                int num = RandInt(N,N+M-1);
                // debug(num,points.size());
                vector<Pos> old_points = points;
                // vector<Pos> new_points = points;
                Pos pos = points[num];
                int diff = 20;
                int x = min(max(0,pos.x+RandInt(diff*(-1),diff)),1000);
                int y = min(max(0,pos.y+RandInt(diff*(-1),diff)),1000);
                // int x = RandInt(50,950);
                // int y = RandInt(50,950);
                // debug(x,y);
                // debug(clock()-ti,__LINE__);
                // points.erase(points.begin() + num);
                // points.insert(points.begin() + num, Pos(x,y,TYPE_STATION));
                points[num] = Pos(x,y,TYPE_STATION);

                // debug(clock()-ti,__LINE__);
                vector<vector<int>> old_distances = distances;
                // debug(clock()-ti,__LINE__);
                distances = update_distance(distances, num);
                // debug(clock()-ti,__LINE__);
                // vector<int> new_route = greedy(distances);
                // debug(clock()-ti,__LINE__);
                // double new_score = calc_score(new_route);
                double new_score = calc_score(route);
                // debug(clock()-ti,__LINE__);
                double T = 30.00 - 29.00 * cnt / 10000.0;
                double probability = exp(min(0.0, (current_score - new_score)/T));
                // if(Randouble() < probability) {
                if(current_score <= new_score) {
                    // if(current_score <= new_score) {
                    //     random++;
                    // }
                    kaizen++;
                    current_score = new_score;
                    // distances = new_distances;
                    // route = new_route;
                }
                else {
                    // 元に戻す
                    distances = old_distances;
                    points = old_points;
                }
            }

                // debug(clock()-ti,__LINE__);
            debug(cnt,kaizen, kaizen*100/cnt,kaizen-random);
        }

        // 2-opt
        {
            double current_score = calc_score(route);
            int ti = clock();
            // int TIMELIMIT = 0.93 * CLOCKS_PER_SEC;
            int TIMELIMIT = limit2 * CLOCKS_PER_SEC;
            int cnt = 1;
            int kaizen = 0;
            int random = 0;
            while(clock() - ti < TIMELIMIT) {
            // for(int t=1; t<400000; t++) {
                cnt++;

                int l = RandInt(1,route.size()-2);
                int r = RandInt(1,route.size()-2);
                while(l == r) {
                    l = RandInt(1,route.size()-2);
                    r = RandInt(1,route.size()-2);
                }
                if(l > r) swap(l,r);

                if(calc_energy(route[l],route[r]) + calc_energy(route[l+1],route[r+1]) 
                    < calc_energy(route[l],route[l+1]) + calc_energy(route[l],route[r+1])) {
                    for(int k=0; k<(r-l)/2; k++) {
                        swap(route[l+1+k],route[r-k]);
                    }
                }

                double new_score = calc_score(route);
                // debug(new_score);
                double T = 30.00 - 28.00 * cnt / 40000.0;
                double probability = exp(min(0.0, (current_score - new_score)/T));
                // if(current_score <= new_score && Randouble() < probability) {
                // if(current_score <= new_score) {
                if(Randouble() < probability) {
                    if(current_score <= new_score) {
                        random++;
                    }
                    kaizen++;
                    current_score = new_score;
                }
                else {
                    // 元に戻す
                    for(int k=0; k<(r-l)/2; k++) {
                        swap(route[l+1+k],route[r-k]);
                    }
                }
            }
            debug(cnt,kaizen, kaizen*100/cnt,kaizen-random);
        }

        // debug(route);  

        output(route);

        calc_score(route); 
    }

    vector<vector<int>> calc_distance() {
        // 全点間エネルギーを計算
        vector<vector<int>> distances(N+M,vector<int>(N+M));
        for(int i=0; i<N+M; i++) {
            for(int j=0; j<N+M; j++) {
                distances[i][j] = calc_energy(i,j);
            }
        }
        // debug(distances);

        // ワーシャルフロイド
        // kを経由した方がエネルギーが少ない場合もある
        for(int k=0; k<N+M; k++) {
            for(int i=0; i<N+M; i++) {
                for(int j=0; j<N+M; j++) {
                    int d = distances[i][k] + distances[k][j];
                    distances[i][j] = min(distances[i][j],d);
                }
            }
        }
        return distances;
    }

    vector<vector<int>> update_distance(vector<vector<int>>& distances, int k) {
        // 全点間エネルギーを計算
        // vector<vector<int>> distances(N+M,vector<int>(N+M));
        // for(int i=0; i<N+M; i++) {
        //     for(int j=0; j<N+M; j++) {
        //         distances[i][j] = calc_energy(i,j);
        //     }
        // }
        // debug(distances);

        // ワーシャルフロイド
        // kを経由した方がエネルギーが少ない場合もある
        // for(int k=0; k<N+M; k++) {
            for(int i=0; i<N+M; i++) {
                for(int j=0; j<N+M; j++) {
                    int d = distances[i][k] + distances[k][j];
                    distances[i][j] = min(distances[i][j],d);
                }
            }
        // }
        return distances;
    }

    vector<int> greedy(vector<vector<int>>& distances) {
        // 惑星1からスタートする
        // 一番近い惑星＋宇宙ステーションを選び続ける
        vector<int> visited(N+M,0);
        vector<int> route;
        visited[0]++;
        route.push_back(0);

        int v = 0;
        for(int i=0; i<N-1; i++) {
            int nearest_dist = INT_MAX;
            int nearest_v = -1;

            // 一番近い惑星を探す
            for(int next=0; next<N; next++) {
                if(visited[next] > 0) continue;

                // int d = calc_energy(v,next);
                int d = distances[v][next];
                if(d < nearest_dist) {
                    nearest_dist = d;
                    nearest_v = next;
                }
                // debug(d);
            }
            // 次の頂点に移動
            // dijkstraで経路を復元
            vector<int> path = djikstra(v,nearest_v);
            for(auto p : path) {
                route.push_back(p);
            }

            v = nearest_v;
            visited[v]++;
            // route.push_back(nearest_v);
        }
        // 最後に惑星1に戻る
        route.push_back(0);
        // debug(visited);
        // debug(route);

        return route;
    }

    vector<int> update_greedy(vector<vector<int>>& distances, vector<int>& route, int k) {
        // 全部通ってるところから
        vector<int> visited(N+M,1);

        // 消した宇宙ステーションを削除する
        visited[k] = 0;
        vector<int> new_route = route;
        for(int i=0; i<route.size(); i++) {
            if(route[i] == k)  {
                // 消した宇宙ステーションを削除
                new_route.erase(new_route.begin()+i);
            }
        }
        route = new_route;
        // vector<int> route;
        // visited[0]++;
        // route.push_back(0);

        int v = 0;
        for(int i=0; i<N-1; i++) {
            int nearest_dist = INT_MAX;
            int nearest_v = -1;

            // 一番近い惑星を探す
            for(int next=0; next<N; next++) {
                if(visited[next] > 0) continue;

                // int d = calc_energy(v,next);
                int d = distances[v][next];
                if(d < nearest_dist) {
                    nearest_dist = d;
                    nearest_v = next;
                }
                // debug(d);
            }
            // 次の頂点に移動
            // dijkstraで経路を復元
            vector<int> path = djikstra(v,nearest_v);
            for(auto p : path) {
                route.push_back(p);
            }

            v = nearest_v;
            visited[v]++;
            // route.push_back(nearest_v);
        }
        // 最後に惑星1に戻る
        route.push_back(0);
        // debug(visited);
        // debug(route);

        return route;
    }

    void output(vector<int>& route) {
        // 宇宙ステーションの座標
        for(int i=N; i<N+M; i++) {
            if(points[i].type == TYPE_STATION) {
                cout << points[i].x << " " << points[i].y << endl;
            }
        }

        // 経路の長さ
        cout << route.size() << endl;

        // 経路
        for(auto i : route) {
            Pos pos = points[i];
            if(pos.type == TYPE_PLANET) {
                cout << pos.type << " " << i+1 << endl;
            }
            else {
                cout << pos.type << " " << i+1-N << endl;
            }
        }
    }

    void set_station() {
        // 宇宙ステーションの座標は適当に決め打ち
        vector<pair<int,int>> v;
        v.push_back({300,300});
        v.push_back({300,500});
        v.push_back({300,700});
        v.push_back({500,300});
        v.push_back({500,700});
        v.push_back({700,300});
        v.push_back({700,500});
        v.push_back({700,700});
        for(int i=0; i<M; i++) {
            // points.emplace_back(Pos(v[i].first,v[i].second,TYPE_STATION));
            points.emplace_back(v[i].first,v[i].second,TYPE_STATION);
            // points.emplace_back(RandInt(0,1000),RandInt(0,1000),TYPE_STATION);
        }
    }

    void TwoOpt(vector<int>& route, vector<vector<int>>& distances) {
        debug(route.size());
        for(int i=1; i<route.size()-3; i++) {
            for(int j=i+2; j<route.size()-1; j++) {
                // debug(i,j);
                // if(distances[route[i]][route[j]] + distances[route[i+1]][route[j+1]] 
                //     < distances[route[i]][route[i+1]] + distances[route[j]][route[j+1]]) {
                if(calc_energy(route[i],route[j]) + calc_energy(route[i+1],route[j+1]) 
                    < calc_energy(route[i],route[i+1]) + calc_energy(route[j],route[j+1])) {
                    for(int k=0; k<(j-i)/2; k++) {
                        // int temp = route[i+1+k];
                        // route[i+1+k] = route[j-k];
                        // route[j-k] = temp;
                        debug(route[i+1+k],route[j-k]);
                        swap(route[i+1+k],route[j-k]);
                    }
                }
            }
        }

    }

    double calc_score(vector<int>& route) {
        ll s = 0;
        for(int i=0; i<route.size()-1; i++) {
            s += calc_energy(route[i],route[i+1]);
        }
        // debug(s);

        double score = round(1000000000/(1000+sqrt(s)));
        // debug(score);
        return score;
    }

    // a以上b以下のランダム
    int RandInt(int a, int b) {
        return a + rand() % (b-a+1);
    }

    // 0以上1以下のランダムな実数を返す
    double Randouble() {
        return 1.0 * rand() / RAND_MAX;
    }

    int calc_energy(int i, int j) {
        int dx, dy;
        int energy;
        auto [x1, y1, type1] = points[i];
        auto [x2, y2, type2] = points[j];
        dx = x1 - x2;
        dy = y1 - y2;
        energy = dx * dx + dy * dy;

        // 惑星かどうか判定
        if (type1 == TYPE_PLANET)
        {
            energy *= 5;
        }
        if (type2 == TYPE_PLANET)
        {
            energy *= 5;
        }
        return energy;
    }

    vector<int> djikstra(int i, int j) {

       	// 二点間の最短距離
        // vector<vector<ll>> dij(N+M);

        // 経路復元用　1つ前にいた頂点を保存
        vector<int> prev_points(N+M,-1);


        // int k = 0;
        // for(int k=0; k<N+M; k++) {
            vector<ll> cur(N+M,INF);
            vector<bool> kakutei(N+M+1,false);
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;

            int start = i;
            cur[start] = 0;
            Q.push(make_pair(cur[start],start));

            while(!Q.empty()) {
                auto[d, pos] = Q.top();
                Q.pop();

                if(kakutei[pos] == true) continue;

                kakutei[pos] = true;
                for(int next=0; next<N+M; next++) {
                    int cost = calc_energy(pos,next);
                    if(cur[next] > cur[pos]+cost) {
                        // 1つ前の点を保存
                        prev_points[next] = pos;
                        // 値を更新
                        cur[next] = cur[pos]+cost;
                        Q.push(make_pair(cur[next],next));
                    }
                }
            }
            // dij[i] = cur;
        // }
        // debug(dij);
        // debug(cur);
        // debug(prev_points);

        // 経路復元
        // ゴールからたどっていく
        int v = j;
        vector<int> path;

        while(v != i) {
            path.push_back(v);
            v = prev_points[v];
        }
        reverse(path.begin(),path.end());

        return path;
    }


};



int main() {
    START_TIME = clock();

    int n,m;
    cin >> n >> m;
    // vector<int> a(n),b(n);
    vector<Pos> points;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a >> b;
        points.emplace_back(Pos(a,b,TYPE_PLANET));
    }
    debug(n,m,points);

    Solver solver(n,m,points);
    solver.solve();

	return 0;
}
yukicoder

結果

テストケース

ソースコード
