結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 15:12:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 287 ms / 1,000 ms |
コード長 | 8,601 bytes |
コンパイル時間 | 1,752 ms |
実行使用メモリ | 6,956 KB |
スコア | 8,237,894 |
最終ジャッジ日時 | 2022-07-30 15:13:20 |
合計ジャッジ時間 | 12,377 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#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 = 100000;float final_T = 20;float TIME_LIMIT = 1000;float TIME_LIMIT_STATION = 200;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;}void greedy_strategy(vector<P> &ans, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_mat){// 訪れていない場所の中で一番コストが小さくいけそうなところにいく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;}for(auto p_pos: dist_mat.at(pos).at(0).second){ans.push_back(p_pos);}}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);}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);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);}}vector<vector<pair<int, vector<P>>>> dist = make_dist_map(stations);/*rep(i, N){sort(dist.at(i).begin(), dist.at(i).end());}*/rep(i, M){cout<<stations.at(i).x<<" "<<stations.at(i).y<<endl;}vector<P> ans;greedy_strategy(ans, stations, dist);cout_ans(ans);return 0;}