結果

問題 No.5007 Steiner Space Travel
ユーザー yunixyunix
提出日時 2022-07-30 15:31:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 944 ms / 1,000 ms
コード長 9,271 bytes
コンパイル時間 1,876 ms
実行使用メモリ 6,952 KB
スコア 8,316,519
最終ジャッジ日時 2022-07-30 15:32:21
合計ジャッジ時間 31,995 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 860 ms
6,948 KB
testcase_01 AC 923 ms
5,028 KB
testcase_02 AC 932 ms
5,108 KB
testcase_03 AC 914 ms
4,968 KB
testcase_04 AC 921 ms
4,968 KB
testcase_05 AC 944 ms
4,972 KB
testcase_06 AC 918 ms
5,084 KB
testcase_07 AC 856 ms
6,952 KB
testcase_08 AC 909 ms
4,916 KB
testcase_09 AC 860 ms
5,084 KB
testcase_10 AC 928 ms
4,956 KB
testcase_11 AC 864 ms
5,160 KB
testcase_12 AC 938 ms
5,076 KB
testcase_13 AC 921 ms
4,968 KB
testcase_14 AC 855 ms
4,956 KB
testcase_15 AC 919 ms
5,088 KB
testcase_16 AC 935 ms
6,952 KB
testcase_17 AC 924 ms
4,912 KB
testcase_18 AC 925 ms
5,168 KB
testcase_19 AC 864 ms
5,008 KB
testcase_20 AC 927 ms
5,204 KB
testcase_21 AC 858 ms
5,092 KB
testcase_22 AC 921 ms
4,916 KB
testcase_23 AC 857 ms
4,952 KB
testcase_24 AC 936 ms
5,012 KB
testcase_25 AC 861 ms
4,956 KB
testcase_26 AC 931 ms
4,920 KB
testcase_27 AC 934 ms
4,972 KB
testcase_28 AC 877 ms
4,964 KB
testcase_29 AC 924 ms
6,948 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
using namespace std;
using vec_int = vector<int>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using ll = long long;
// using PQ = priority_queue<pair<float, int>, vector<pair<float,int>>, greater<pair<float, int>>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

float initial_T = 10000;
float final_T = 2000;
float TIME_LIMIT = 1000;
float TIME_LIMIT_STATION = 10;

int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
int N_VERTICAL = 10;

vector<P> DIRS = {make_pair(0, -1), make_pair(-1, 0), make_pair(0, 1), make_pair(1, 0)};

bool is_in(int x, int y, int N)
{
    if (x >= 0 && x < N && y >= 0 && y < N)
        return true;
    return false;
}

// std::mt19937 mt{ std::random_device{}() };
std::mt19937 mt{12345};
std::uniform_int_distribution<int> dist(1, RAND_RANGE);
float get_time(bool init)
{
    static std::chrono::system_clock::time_point start;
    if (init)
    {
        start = std::chrono::system_clock::now();
    }
    std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); //処理に要した時間をミリ秒に変換
}


class Rand
{
private:
    int count = 0;
    vec_int rand_arr;

public:
    Rand(){
        rep(i, RAND_ARR_LEN){
            rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;

int Rand::get()
{
    int num = rand_arr.at(count);
    count += 1;
    count %= RAND_ARR_LEN;
    return num;
}

int Rand::get_rand(int from, int to)
{
    int diff = to - from;
    int num = get() % diff;
    return num + from;
}

float Rand::get_float()
{
    // 0~1の間の一様乱数
    return (float)get() / (float)RAND_RANGE;
}

Rand ro;

float current_tmp_station(float current_time)
{
    return final_T + (initial_T - final_T) * (TIME_LIMIT_STATION - current_time) / TIME_LIMIT_STATION;
}

bool is_valid_transition_station(int diff, float current_time)
{
    float t = current_tmp_station(current_time);
    float rand = ro.get_float();
    // cerr<<"tmperature"<<t<<" "<<diff<<endl;
    return rand < exp(((float)diff) / t);
}


int N, M; 
vec_int a, b;
int alpha=5;
int sq_alpha=25;


class SpaceStation{
    public:
    int x;
    int y;
    SpaceStation(){
        x=0;
        y=0;
    };
    SpaceStation(int xpos, int ypos){
        x=xpos;
        y=ypos;
    };
    int square_distance(int x2, int y2){
        return (x2-x)*(x2-x) + (y2-y)*(y2-y);
    };
    void set_pos(int xpos, int ypos){
        x=xpos;
        y=ypos;
    };

    void random_move(){
        int dx = ro.get_rand(-20, 21);
        int dy = ro.get_rand(-20, 21);
        int x2 = x+dx;
        int y2 = y+dy;
        x2 = max(0, x2);
        y2 = max(0, y2);
        x2 = min(1000, x2);
        y2 = min(1000, y2);
        x=x2;
        y=y2;
    }
};

int tot_distance(vector<SpaceStation> &stations){
    int result = 0;
    rep(i, N){
        int tmp_dist = INT_MAX;
        rep(j, M){
            tmp_dist = min(tmp_dist, stations.at(j).square_distance(a.at(i), b.at(i)));
        }
        result += tmp_dist;
    }
    return result;
}

void cout_ans(vector<P> &ans){
    cout<<ans.size()<<endl;
    rep(i, ans.size()){
        cout<<ans.at(i).first<<" "<<ans.at(i).second+1<<endl;
    }
}

int sq_dist_between_cities(int i, int j){
    int result = 0;
    result += (a.at(i)-a.at(j))*(a.at(i)-a.at(j));
    result += (b.at(i)-b.at(j))*(b.at(i)-b.at(j));
    return result;

}

vector<vector<pair<int, vector<P>>>> make_dist_map(vector<SpaceStation> &stations){
    vector<vector<pair<int, vector<P>>>> result(N, vector<pair<int, vector<P>>>(N+M));

    for(int i=0;i<N;i++){
        // 歳iをstartにする
        vector<int> visited(N+M, 0);
        vector<int> prev_city(N, -1);

        priority_queue<T, vector<T>, greater<T>> pq;
        pq.emplace(0, i, -1);

        while(!pq.empty()){
            int dist, pos, prev; tie(dist, pos, prev) = pq.top(); pq.pop();
            if(visited.at(pos)==1)continue;
            if(pos<N){
                // 都市にたどり着いた時
                visited.at(pos) = 1;
                vector<P> route;
                if(prev!=-1){
                    route = result.at(i).at(prev).second;
                }
                route.push_back(make_pair(1, pos));
                result.at(i).at(pos) = make_pair(dist, route);

                for(int j=0;j<N;j++){
                    // 都市にいく時
                    if(visited.at(j)==1)continue;
                    int add_dist = sq_dist_between_cities(pos, j) * sq_alpha;
                    pq.emplace(dist+add_dist, j, pos);
                }
                for(int j=0;j<M;j++){
                    // ステーションにいく時
                    if(visited.at(j)==1)continue;
                    int add_dist = stations.at(j).square_distance(a.at(pos), b.at(pos)) * alpha;
                    pq.emplace(dist+add_dist, j+N, pos);
                }
            }else{
                // 宇宙ステーションにたどり着いた時
                visited.at(pos) = 1;
                vector<P> route;
                if(prev!=-1){
                    route = result.at(i).at(prev).second;
                }
                route.push_back(make_pair(2, pos-N));
                result.at(i).at(pos) = make_pair(dist, route);

                for(int j=0;j<N;j++){
                    // 都市にいく時
                    if(visited.at(j)==1)continue;
                    int add_dist = stations.at(pos-N).square_distance(a.at(j), b.at(j))*alpha;
                    pq.emplace(dist+add_dist, j, pos);
                }
                for(int j=0;j<M;j++){
                    // ステーションにいく時
                    if(visited.at(j)==1)continue;
                    int add_dist = stations.at(pos-N).square_distance(stations.at(j).x, stations.at(j).y);
                    pq.emplace(dist+add_dist, j+N, pos);
                }
            }
        }
    }
    return result;
}

int greedy_strategy(vector<P> &ans, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_mat){
    // 訪れていない場所の中で一番コストが小さくいけそうなところにいく
    int result = 0;

    int pos = 0;
    ans.push_back(make_pair(1, 0));

    vec_int visited(N, 0);
    while(true){
        visited.at(pos) = true;
        
        int min_dist = INT_MAX;
        int next_pos = -1;
        for(int i=0;i<N;i++){
            if(visited.at(i)==1)continue;
            int tmp_dist = dist_mat.at(pos).at(i).first;
            if(min_dist>tmp_dist){
                min_dist = tmp_dist;
                next_pos = i;
            }
        }


        if(next_pos==-1)break;

        for(auto p_pos: dist_mat.at(pos).at(next_pos).second){
            ans.push_back(p_pos);
        }
        pos = next_pos;
        result += min_dist;
    }

    for(auto p_pos: dist_mat.at(pos).at(0).second){
        ans.push_back(p_pos);
        result += dist_mat.at(pos).at(0).first;
    }
    return result;
}

int main(){
    get_time(true);
    cin>>N>>M;
    rep(i, N){
        int aa, bb; cin>>aa>>bb;
        a.push_back(aa);
        b.push_back(bb);
    }

    int tot_dist = INT_MAX;
    vector<P> ans;
    vector<SpaceStation> ans_stations;
    while(get_time(false)<TIME_LIMIT*0.85){
        float start_time = get_time(false);
    
        vector<SpaceStation> stations(M);
        rep(i, M){
            stations.at(i) = SpaceStation(ro.get_rand(0, 1001), ro.get_rand(0, 1001));
        }

        int station_score = tot_distance(stations);

        cerr<<"initial tot square distance:"<<station_score<<endl;
        while(true){
            float ct = get_time(false)-start_time;
            if(ct>TIME_LIMIT_STATION)break;
            int selected_station = ro.get_rand(0, M);
            int old_x = stations.at(selected_station).x;
            int old_y = stations.at(selected_station).y;
            stations.at(selected_station).random_move();

            int new_score = tot_distance(stations);

            int diff = new_score-station_score;
            if(is_valid_transition_station(-1*diff, ct)){//小さくなる方がいい
                station_score = new_score;
            }else{
                stations.at(selected_station).set_pos(old_x, old_y);
            }
        }
        cerr<<"annealed tot square distance:"<<station_score<<endl;

        cerr<<"time1:"<<get_time(false)<<endl;
        vector<vector<pair<int, vector<P>>>> dist = make_dist_map(stations);
        cerr<<"time2:"<<get_time(false)<<endl;

        vector<P> tmp_ans;
        int tmp_dist = greedy_strategy(tmp_ans, stations, dist);
        if(tmp_dist<tot_dist){
            tot_dist = tmp_dist;
            ans = tmp_ans;
            ans_stations = stations;
        }
         
    }
         rep(i, M){
            cout<<ans_stations.at(i).x<<" "<<ans_stations.at(i).y<<endl;
        }

   

    cout_ans(ans);
    return 0;


}
0