結果

問題 No.5007 Steiner Space Travel
ユーザー tmikadatmikada
提出日時 2023-04-30 13:26:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 990 ms / 1,000 ms
コード長 11,592 bytes
コンパイル時間 3,700 ms
コンパイル使用メモリ 229,304 KB
実行使用メモリ 4,496 KB
スコア 7,385,470
最終ジャッジ日時 2023-04-30 13:27:19
合計ジャッジ時間 36,100 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 960 ms
4,368 KB
testcase_01 AC 983 ms
4,368 KB
testcase_02 AC 983 ms
4,496 KB
testcase_03 AC 983 ms
4,372 KB
testcase_04 AC 960 ms
4,368 KB
testcase_05 AC 959 ms
4,372 KB
testcase_06 AC 985 ms
4,368 KB
testcase_07 AC 989 ms
4,368 KB
testcase_08 AC 984 ms
4,368 KB
testcase_09 AC 962 ms
4,372 KB
testcase_10 AC 959 ms
4,368 KB
testcase_11 AC 985 ms
4,368 KB
testcase_12 AC 985 ms
4,368 KB
testcase_13 AC 984 ms
4,372 KB
testcase_14 AC 990 ms
4,372 KB
testcase_15 AC 961 ms
4,368 KB
testcase_16 AC 984 ms
4,372 KB
testcase_17 AC 985 ms
4,368 KB
testcase_18 AC 987 ms
4,368 KB
testcase_19 AC 964 ms
4,368 KB
testcase_20 AC 959 ms
4,372 KB
testcase_21 AC 986 ms
4,368 KB
testcase_22 AC 984 ms
4,376 KB
testcase_23 AC 985 ms
4,368 KB
testcase_24 AC 964 ms
4,372 KB
testcase_25 AC 962 ms
4,368 KB
testcase_26 AC 983 ms
4,372 KB
testcase_27 AC 986 ms
4,368 KB
testcase_28 AC 982 ms
4,372 KB
testcase_29 AC 959 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 current_score = calc_score(route);
            int ti = clock();
            int TIMELIMIT = 0.20 * CLOCKS_PER_SEC;
            int cnt = 1;
            int kaizen = 0;
            while(clock() - ti < TIMELIMIT) {
                cnt++;
                // ずらす宇宙ステーションをランダムに選ぶ
                int num = RandInt(N,N+M-1);
                // debug(num,points.size());
                points.erase(points.begin() + num);
                points.emplace_back(RandInt(1,1000),RandInt(1,1000),TYPE_STATION);
            }
            vector<vector<int>> new_distances = calc_distance();
            vector<int> new_route = greedy(new_distances);
                double new_score = calc_score(new_route);
                if(current_score <= new_score) {
                    kaizen++;
                    current_score = new_score;
                    distances = new_distances;
                    route = new_route;
                }
                else {
                    // 元に戻す
                }

            debug(cnt,kaizen, kaizen*100/cnt);
        }

        // 2-opt
        {
            double current_score = calc_score(route);
            int ti = clock();
            // int TIMELIMIT = 0.93 * CLOCKS_PER_SEC;
            int TIMELIMIT = (0.93-0.20) * CLOCKS_PER_SEC;
            int cnt = 1;
            int kaizen = 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);
                // double T = 30.00 - 28.00 * cnt / 400000.0;
                // double probability = exp(min(0.0, (current_score - new_score)/T));
                // if(current_score <= new_score && Randouble() < probability) {
                if(current_score <= new_score) {
                    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);
        }

        // 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<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;
    }

    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;
}
0