結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 yunix
|
| 提出日時 | 2022-08-02 22:54:10 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 987 ms / 1,000 ms |
| コード長 | 22,853 bytes |
| コンパイル時間 | 2,155 ms |
| 実行使用メモリ | 4,980 KB |
| スコア | 8,703,843 |
| 最終ジャッジ日時 | 2022-08-02 22:54:45 |
| 合計ジャッジ時間 | 35,087 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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_STATION = 5000;
float final_T_STATION = 100;
float initial_T = 500;
float final_T = 100;
float TIME_LIMIT = 1000;
float TIME_LIMIT_STATION = 1000;
float TIME_LIMIT_TSP = 30;
float TIME_LIMIT_TSP2 = 600;
int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
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_STATION + (initial_T_STATION - final_T_STATION) * (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);
}
float current_tmp_tsp(float current_time)
{
return final_T + (initial_T - final_T) * (TIME_LIMIT - current_time) / TIME_LIMIT;
}
bool is_valid_transition_tsp(int diff, float current_time)
{
float t = current_tmp_tsp(current_time);
float rand = ro.get_float();
return rand < exp(((float)diff) / t);
}
float current_tmp_tsp2(float current_time)
{
return final_T + (initial_T - final_T) * (TIME_LIMIT_TSP2 - current_time) / TIME_LIMIT_TSP2;
}
bool is_valid_transition_tsp2(int diff, float current_time)
{
float t = current_tmp_tsp2(current_time);
float rand = ro.get_float();
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 intermediate_distance(int city1, int city2){
int result = 0;
result += square_distance(a.at(city1), b.at(city1))*alpha;
result += square_distance(a.at(city2), b.at(city2))*alpha;
return result;
}
};
int tot_distance(vector<SpaceStation> &stations, vec_int &excluded){
int result = 0;
rep(i, N){
if(excluded.at(i)==1)continue;
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;
}
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<vector<pair<int, vector<P>>>> result(N, vector<pair<int, vector<P>>>(N));
vector<vector<int>> visited(N, vec_int(N, 0));
for(int i=0;i<N;i++){
// 都市iをstartにする
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(i).at(pos)==1)continue;
// 都市にたどり着いた時
visited.at(i).at(pos) = 1;
visited.at(pos).at(i) = 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);
vector<P> route2 = route;
reverse(route2.begin(), route2.end());
result.at(pos).at(i) = make_pair(dist, route2);
for(int j=0;j<N;j++){
// 都市にいく時
if(visited.at(i).at(j)==1)continue;
int add_dist = sq_dist_between_cities(pos, j) * sq_alpha;
pq.emplace(dist+add_dist, j, pos);
}
}
}
return result;
}
int calc_dist(vector<SpaceStation> &stations, vector<P> &tmp_ans){
int result = 0;
for(int i=1;i<tmp_ans.size();i++){
int type, pos; tie(type, pos) = tmp_ans.at(i);
int prev_type, prev_pos; tie(prev_type, prev_pos) = tmp_ans.at(i-1);
if(type==1&&prev_type==1){
result += sq_dist_between_cities(pos, prev_pos)*sq_alpha;
}else if(type==1&&prev_type==2){
result += stations.at(prev_pos).square_distance(a.at(pos), b.at(pos))*alpha;
}else if(type==2 && prev_type==1){
result += stations.at(pos).square_distance(a.at(prev_pos), b.at(prev_pos))*alpha;
}else{
result += stations.at(pos).square_distance(stations.at(prev_pos).x, stations.at(prev_pos).y);
}
}
return result;
}
int check_keiyu(vector<SpaceStation> &stations, vec_int &keiyu_flag, vec_int &routes, vector<vector<pair<int, vector<P>>>> &dist_map){
int result = 0;
rep(i, N){
int prev = routes.at(i);
int current = routes.at(i+1);
int original_distance = dist_map.at(prev).at(current).first;
int after_distance = INT_MAX;
int keiyu = -1;
rep(j, M){
int dist = 0;
dist += stations.at(j).square_distance(a.at(prev), b.at(prev))*5;
dist += stations.at(j).square_distance(a.at(current), b.at(current))*5;
if(after_distance>dist){
after_distance = dist;
keiyu = j;
}
}
if(after_distance<original_distance){
result += original_distance - after_distance;
keiyu_flag.at(i) = keiyu;
}
}
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) = 1;
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;
int tmp_dist2 = calc_dist(stations, ans);
for(auto p_pos: dist_mat.at(pos).at(next_pos).second){
// if(p_pos.second == pos&&p_pos.first==1)continue;
if(ans.at(ans.size()-1)==p_pos)continue;
ans.push_back(p_pos);
}
int tmp_dist3 = calc_dist(stations, ans);
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;
}
void adjust_station_pos(vector<SpaceStation> &stations, vector<P> &tmp_ans){
vector<vec_int> station_connections(M);
rep(i, tmp_ans.size()){
if(tmp_ans.at(i).first==2){
int st = tmp_ans.at(i).second;
if(tmp_ans.at(i-1).first==1){
station_connections.at(st).push_back(tmp_ans.at(i-1).second);
}
if(tmp_ans.at(i+1).first==1){
station_connections.at(st).push_back(tmp_ans.at(i+1).second);
}
}
}
for(int station = 0;station<M;station++){
int x = stations.at(station).x;
int y = stations.at(station).y;
int min_dist = INT_MAX;
int best_x = x;
int best_y = y;
for(int dx=-100;dx<=100;dx+=2){
for(int dy=-100;dy<=100;dy+=2){
int tot_dist = 0;
int x2 = x+dx;
int y2 = y+dy;
if(!(0<=x2 && x2<=1000 && 0<=y2 && y2<=1000))continue;
stations.at(station).x = x2;
stations.at(station).y = y2;
for(auto star: station_connections.at(station)){
tot_dist += stations.at(station).square_distance(a.at(star), b.at(star));
}
if(tot_dist<min_dist){
min_dist = tot_dist;
best_x = x2;
best_y = y2;
}
}
}
stations.at(station).x=best_x;
stations.at(station).y=best_y;
}
}
vector<int> find_initial_route(vector<vector<pair<int, vector<P>>>> &dist_map){
int pos = 0;
vec_int visited(N, 0);
vec_int result;
while(true){
result.push_back(pos);
visited.at(pos) = 1;
int min_dist = INT_MAX;
int min_pos = -1;
for(int i=0;i<N;i++){
if(visited.at(i)==1)continue;
if(min_dist>dist_map.at(pos).at(i).first){
min_dist = dist_map.at(pos).at(i).first;
min_pos = i;
}
}
if(min_pos==-1)break;
pos=min_pos;
}
result.push_back(0);
return result;
}
void cout_ans(vector<int> &route, vector<vector<pair<int, vector<P>>>> &dist_map, vec_int &keiyu_flag){
vector<P> result;
for(int i=1;i<route.size();i++){
int prev = route.at(i-1);
int current = route.at(i);
if(keiyu_flag.at(i-1)==-1){
for(auto pos: dist_map.at(prev).at(current).second){
result.push_back(pos);
}
}else{
result.push_back(make_pair(1, prev));
result.push_back(make_pair(2, keiyu_flag.at(i-1)));
result.push_back(make_pair(1, current));
}
}
cout<<result.size()<<endl;
rep(i, result.size()){
cout<<result.at(i).first<<" "<<result.at(i).second+1<<endl;
}
}
void tsp(vec_int &route, vector<vector<pair<int, vector<P>>>> &dist_map){
float start_time = get_time(false);
int current_length = 0;
rep(i, N){
current_length += dist_map.at(route.at(i)).at(route.at(i+1)).first;
}
while(true){
float ct = get_time(false)-start_time;
if(ct>TIME_LIMIT_TSP)break;
int ind1 = ro.get_rand(0, N);
int ind2 = ro.get_rand(0, N);
if(ind1==ind2)continue;
int length1 = dist_map.at(route.at(ind1)).at(route.at(ind1+1)).first;
int length2 = dist_map.at(route.at(ind2)).at(route.at(ind2+1)).first;
int length1_2 = dist_map.at(route.at(ind1)).at(route.at(ind2)).first;
int length2_2 = dist_map.at(route.at(ind1+1)).at(route.at(ind2+1)).first;
int diff = length1_2 + length2_2 - length1-length2;
if(is_valid_transition_tsp(-1*diff, ct)){
vec_int route2 = route;
for(int i=ind1+1; i<=ind2;i++){
route.at(i) = route2.at(ind2-(i-(ind1+1)));
}
}
}
return;
}
void tsp2(vec_int &route, vector<vector<pair<int, vector<P>>>> &dist_map, vec_int &keiyu_flag, vector<SpaceStation> &stations){
float start_time = get_time(false);
// int current_length = check_keiyu
int current_length = check_keiyu(stations, keiyu_flag, route, dist_map);
while(true){
float ct = get_time(false)-start_time;
if(ct>TIME_LIMIT_TSP)break;
int ind1 = ro.get_rand(0, N);
int ind2 = ro.get_rand(0, N);
if(ind1==ind2)continue;
int length1 = dist_map.at(route.at(ind1)).at(route.at(ind1+1)).first;
int length2 = dist_map.at(route.at(ind2)).at(route.at(ind2+1)).first;
int length1_2 = dist_map.at(route.at(ind1)).at(route.at(ind2)).first;
int length2_2 = dist_map.at(route.at(ind1+1)).at(route.at(ind2+1)).first;
int diff = length1_2 + length2_2 - length1-length2;
if(is_valid_transition_tsp2(-1*diff, ct)){
vec_int route2 = route;
for(int i=ind1+1; i<=ind2;i++){
route.at(i) = route2.at(ind2-(i-(ind1+1)));
}
}
}
return;
}
vec_int annealing(vec_int &route, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_map){
vec_int distance(N);
vec_int keiyu(N, -1);
for(int i=0;i<N;i++){
// i - i+1の間で何処か別のところを経由させると良いことがあるかをチェックする
int prev = route.at(i);
int current = route.at(i+1);
int original_distance = dist_map.at(prev).at(current).first;
int after_dist = INT_MAX;
int keiyu_station = -1;
for(int j=0;j<M;j++){
int tmp = stations.at(j).intermediate_distance(prev, current);
if(after_dist>tmp){
after_dist = tmp;
keiyu_station = j;
}
}
if(after_dist>original_distance){
distance.at(i) = original_distance;
}else{
distance.at(i) = after_dist;
keiyu.at(i) = keiyu_station;
}
}
int tot_distance = 0;
rep(i, N)tot_distance += distance.at(i);
int count = 0;
while(true){
// cerr<<"count:"<<count<<endl;
float ct = get_time(false);
if(ct>=TIME_LIMIT*0.98)break;
if(count<0){
// 2-opt
int a = ro.get_rand(0, N);
int b = ro.get_rand(0, N);
if(abs(a-b)<=1)continue;
int city1 = min(a, b);
int city2 = max(a, b);
// cerr<<city1<<" "<<city2<<endl;
int original_distance = distance.at(city1);
original_distance += distance.at(city2);
int after1 = dist_map.at(route.at(city1)).at(route.at(city2)).first;
int keiyu1 = -1;
for(int j=0;j<M;j++){
int tmp1 = stations.at(j).intermediate_distance(route.at(city1), route.at(city2));
if(after1>tmp1){
after1 = tmp1;
keiyu1 = j;
}
}
int after2 = dist_map.at(route.at(city1+1)).at(route.at(city2+1)).first;
int keiyu2 = -1;
for(int j=0;j<M;j++){
int tmp2 = stations.at(j).intermediate_distance(route.at(city1+1), route.at(city2+1));
if(after2>tmp2){
after2 = tmp2;
keiyu2 = j;
}
}
int diff = (original_distance-(after1+after2));
if(is_valid_transition_tsp(diff, ct)){
// cerr<<"valid"<<endl;
tot_distance -= original_distance;
tot_distance += after1+after2;
vec_int route2 = route;
vec_int keiyu_vec2 = keiyu;
vec_int distance2 = distance;
for(int i=city1+1;i<=city2;i++){
route.at(i) = route2.at(city2-(i-(city1+1)));
keiyu.at(i) = keiyu_vec2.at(city2-(i-(city1+1)));
distance.at(i) = distance2.at(city2-(i-(city1+1)));
keiyu.at(city1) = keiyu1;
distance.at(city1) = after1;
keiyu.at(city2) = keiyu2;
distance.at(city2) = after2;
}
}
}else{
// stationを少し動かす
int index = ro.get_rand(0, M);
int x2, y2;
int original_x = stations.at(index).x;
int original_y = stations.at(index).y;
if(count%11!=0){
int dx = ro.get_rand(-150, 151);
int dy = ro.get_rand(-150, 151);
x2 = original_x + dx;
y2 = original_y + dy;
x2 = min(1000, x2);
x2 = max(0, x2);
y2 = min(1000, y2);
y2 = max(0, y2);
}else{
x2 = ro.get_rand(0, 1001);
y2 = ro.get_rand(0, 1001);
}
stations.at(index).x = x2;
stations.at(index).y = y2;
int diff = 0; //after - before
for(int i=0;i<N;i++){
int prev = route.at(i);
int current = route.at(i+1);
if(keiyu.at(i)==index){
int dist1 = distance.at(i);
int tmp = stations.at(index).intermediate_distance(prev, current);
tmp = min(tmp, dist_map.at(prev).at(current).first);
diff += tmp-dist1;
}else{
int dist1 = distance.at(i);
int tmp = stations.at(index).intermediate_distance(prev, current);
if(dist1>tmp){
diff += tmp-dist1;
}
}
}
if(is_valid_transition_station(-1*diff, ct)){
// cerr<<"diff:"<<-1*diff<<endl;
for(int i=0;i<N;i++){
int prev = route.at(i);
int current = route.at(i+1);
if(keiyu.at(i)==index){
int dist1 = distance.at(i);
int tmp = stations.at(index).intermediate_distance(prev, current);
// tmp = min(tmp, dist_map.at(prev).at(current).first);
// diff += tmp-dist1;
if(tmp<dist_map.at(prev).at(current).first){
distance.at(i) = tmp;
keiyu.at(i) = index;
}else{
distance.at(i) = dist_map.at(prev).at(current).first;
keiyu.at(i) = -1;
}
tot_distance -= dist1;
tot_distance += distance.at(i);
}else{
int dist1 = distance.at(i);
int tmp = stations.at(index).intermediate_distance(prev, current);
if(dist1>tmp){
distance.at(i) = tmp;
keiyu.at(i) = index;
}
tot_distance -= dist1;
tot_distance += distance.at(i);
}
}
}else{
stations.at(index).x = original_x;
stations.at(index).y = original_y;
}
}
count++;
if(count==300)count=0;
}
/*
for(int i=0;i<N;i++){
// i - i+1の間で何処か別のところを経由させると良いことがあるかをチェックする
int prev = route.at(i);
int current = route.at(i+1);
int original_distance = dist_map.at(prev).at(current).first;
int after_dist = INT_MAX;
int keiyu_station = -1;
for(int j=0;j<M;j++){
int tmp = stations.at(j).intermediate_distance(prev, current);
if(after_dist>tmp){
after_dist = tmp;
keiyu_station = j;
}
}
if(after_dist>original_distance){
distance.at(i) = original_distance;
}else{
distance.at(i) = after_dist;
keiyu.at(i) = keiyu_station;
}
}
*/
cerr<<"final_count:"<<count<<endl;
return keiyu;
}
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<vector<pair<int, vector<P>>>> dist_map = make_dist_map();
vec_int route = find_initial_route(dist_map);
tsp(route, dist_map);
vector<SpaceStation> stations(M);
rep(i, M){
stations.at(i) = SpaceStation(ro.get_rand(0, 1001), ro.get_rand(0, 1001));
}
vec_int keiyu_flag = annealing(route, stations, dist_map);
/*
int current_reduction = check_keiyu(stations, keiyu_flag, route, dist_map);
vec_int best_keiyu;
while(true){
float ct = get_time(false);
if(ct>180)break;
int ind = ro.get_rand(0, M);
int original_x = stations.at(ind).x;
int original_y = stations.at(ind).y;
int dx = ro.get_rand(-50, 51);
int dy = ro.get_rand(-50, 51);
int x2 = original_x + dx;
int y2 = original_y + dy;
x2 = min(1000, x2);
y2 = min(1000, y2);
x2 = max(0, x2);
y2 = max(0, y2);
stations.at(ind).x = x2;
stations.at(ind).y = y2;
int after_reduction = check_keiyu(stations, keiyu_flag, route, dist_map);
int diff = after_reduction - current_reduction;
if(diff>=0){
current_reduction = after_reduction;
best_keiyu = keiyu_flag;
}else{
stations.at(ind).x = original_x;
stations.at(ind).y = original_y;
}
}
*/
rep(i, M){
cout<<stations.at(i).x<<" "<<stations.at(i).y<<endl;
}
cout_ans(route, dist_map, keiyu_flag);
rep(i, N){
cerr<<"i:"<<i<<" "<<route.at(i)<<" "<<keiyu_flag.at(i)<<endl;
}
return 0;
}