結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 rinrion
|
| 提出日時 | 2022-08-07 16:41:25 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 957 ms / 1,000 ms |
| コード長 | 6,446 bytes |
| コンパイル時間 | 2,074 ms |
| 実行使用メモリ | 4,604 KB |
| スコア | 8,129,843 |
| 最終ジャッジ日時 | 2022-08-07 16:41:58 |
| 合計ジャッジ時間 | 33,616 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
#include<chrono>
using namespace std;
long double ENG(int x1,int y1, int x2, int y2,int t){//エネルギー計算 座標と定数を入力
long double uq= sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return uq*uq*t;
}
long SCORE(long double s){
return (long)(1000000000/(1000+sqrt(s)));
}
static uint32_t randxor(){//ランダム数(int)
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
static double rand01(){//ランダム数(0.0以上1.0未満の小数)
return(randxor()+0.5)*(1.0/UINT_MAX);
}
double timelmt_1=200,timelmt_2=950;
double gettime;
chrono::system_clock::time_point time_now;
chrono::system_clock::time_point time_start = chrono::system_clock::now();
double start_temp_1=500, start_temp_2=5, end_temp=0.001,temp;
int main(){
int n,m;
cin>>n>>m;
vector<int>a(n),b(n);
for(int i=0; i<n; i++){
cin>>a[i]>>b[i];
}
vector<vector<long double>>eng(100,vector<long double>(100)),eng_t;
vector<vector<pair<long double,int>>>eng_sr(100,vector<pair<long double,int>>(100));
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
if(i!=j) eng[i][j]=ENG(a[i],b[i],a[j],b[j],25);
else eng[i][j]=1000000000001;
eng_sr[i][j]=make_pair(eng[i][j],j);
}
sort(eng_sr[i].begin(),eng_sr[i].end());//eng_srのみエネルギーを昇順に並べ替え
}
vector<int>c,c_best,d,d_best;//ロボてりーの位置 最初は均等に置く
c.push_back(250),d.push_back(250);
c.push_back(250),d.push_back(500);
c.push_back(250),d.push_back(750);
c.push_back(500),d.push_back(250);
c.push_back(500),d.push_back(750);
c.push_back(750),d.push_back(250);
c.push_back(750),d.push_back(500);
c.push_back(750),d.push_back(750);
vector<int>tr,tr_best;//惑星を回る順番
bitset<100>visited;
int now=0;
visited[now]=true;
tr.push_back(0);
while(true){//一番近い惑星に行く
bool jdg=false;
for(int i=0; i<99; i++){
if(!(visited[eng_sr[now][i].second])){
int next=eng_sr[now][i].second;
tr.push_back(next);
now=next;
visited[next]=true;
jdg=true;
break;
}
}
if(!jdg)break;
}
tr.push_back(0);
long double eng_sum=0;//消費エネルギー総和
for(int i=0; i<100; i++){
eng_sum+=eng[tr[i]][tr[i+1]];
}
long score,score_t,score_best;
score=SCORE(eng_sum);
score_best=score;
tr_best=tr;
int cnt1=0,cnt1_rec=0;
int cnt2=0,cnt2_rec=0;
while(gettime<timelmt_1){//回る順
if((int)cnt1%5000==0){
time_now = chrono::system_clock::now();
gettime = chrono::duration_cast<chrono::milliseconds>(time_now-time_start).count();
temp=start_temp_1+(end_temp-start_temp_1)*gettime/timelmt_1;
}
int A=randxor()%99+1, B=randxor()%99+1;
int na=tr[A-1],a=tr[A],an=tr[A+1];
int nb=tr[B-1],b=tr[B],bn=tr[B+1];
long double eng_m=eng[na][a]+eng[a][an]+eng[nb][b]+eng[b][bn];
long double eng_p=eng[na][b]+eng[b][an]+eng[nb][a]+eng[a][bn];
int score_r=SCORE(eng_sum-eng_m+eng_p);
double prob=exp((score_r-score)/temp);
double rnd_d=rand01();
//cout<<score_r-score<<" "<<fixed<<setprecision(3)<<prob<<" "<<rnd_d;
if(prob>rnd_d){
tr[A]=b,tr[B]=a;
eng_sum=eng_sum-eng_m+eng_p;
score=score_r;
if(score>score_best){
tr_best=tr;
score_best=score;
}
cnt1_rec++;
}
cnt1++;
}
score=score_best;
bitset<100>check,check_best;
map<int,int>st,st_best;
//ステーション位置
while(gettime<timelmt_2){
if((cnt1+cnt2)%500==0){
time_now = chrono::system_clock::now();
gettime = chrono::duration_cast<chrono::milliseconds>(time_now-time_start).count();
temp=start_temp_2+(end_temp-start_temp_2)*(gettime/(timelmt_2-timelmt_1));
}
eng_t=eng;
bitset<100>check_t;//この惑星からステーションに行くか
map<int,int>st_t;//この惑星から行くステーションの番号
vector<int>c_t=c, d_t=d;
int rnd_st=randxor()%8, rnd_dis=randxor()%5+1,rnd_dir=randxor()%4;
if(rnd_dir==0) c_t[rnd_st]=min(1000,c[rnd_st]+rnd_dis);
else if(rnd_dir==1) c_t[rnd_st]=max(0,c[rnd_st]-rnd_dis);
else if(rnd_dir==2) d_t[rnd_st]=min(1000,d[rnd_st]+rnd_dis);
else d_t[rnd_st]=max(0,d[rnd_st]-rnd_dis);
for(int j=0; j<100; j++){//すべての惑星間のルートについて
int w1=tr_best[j],w2=tr_best[j+1];//惑星w1からw2へのルートについて調べる
for(int i=0; i<8; i++){//すべてのステーションについて
long double eng_b=eng_t[w1][w2];//惑星w1→惑星w2のエネルギー(test値,他のステーション経由の最小値と比較)
//惑星w1→ステーションi→惑星w2のエネルギー
long double eng_c=ENG(a[w1],b[w1],c_t[i],d_t[i],5)+ENG(c_t[i],d_t[i],a[w2],b[w2],5);
if(eng_b>eng_c){//ステーションiを経由した方がエネルギーが少ないなら(他のステーションとも比べる)
eng_t[w1][w2]=eng_c;//w1-w2のエネルギー(test)を変更する
check_t[w1]=true;//w1の次はステーション
st_t[w1]=i;//w1から行くステーションはi
}
}//惑星間の全ルート
}//全ステーション
eng_sum=0;//消費エネルギー総和をtest値で計算しなおす
for(int i=0; i<100; i++){
eng_sum+=eng_t[tr_best[i]][tr_best[i+1]];
}
score_t=SCORE(eng_sum);//scoreを計算しなおす
double prob=exp((score_t-score)/temp);
double rnd_d=rand01();
if(prob>rnd_d){
score=score_t;
check=check_t;
st=st_t;
c=c_t;
d=d_t;
cnt2_rec++;
/*
cout<<"rec score "<<score<<endl;
for(int i=0; i<8; i++){
cout<<c[i]<<" "<<d[i]<<endl;
}
int b_c=check.count();
cout<<101+b_c<<endl;
for(int i=0; i<101; i++){
cout<<1<<" "<<tr_best[i]+1<<endl;
if(check[tr_best[i]]) cout<<2<<" "<<st[tr_best[i]]+1<<endl;
}
*/
}
if(score>score_best){//best更新なら
score_best=score;
check_best=check;
st_best=st;
c_best=c;
d_best=d;
}
cnt2++;
}
for(int i=0; i<8; i++){
cout<<c_best[i]<<" "<<d_best[i]<<endl;
}
int b_c=check_best.count();
cout<<101+b_c<<endl;
for(int i=0; i<101; i++){
cout<<1<<" "<<tr_best[i]+1<<endl;
if(check_best[tr_best[i]]) cout<<2<<" "<<st_best[tr_best[i]]+1<<endl;
}
// cout<<"score "<<score_best<<" cnt1 "<<cnt1<<" "<<fixed<<setprecision(2)<<(double)cnt1_rec/cnt1<<" cnt2 "<<cnt2<<" cnt2_rec "<<cnt2_rec<<" "<<fixed<<setprecision(2)<<(double)cnt2_rec/cnt2<<endl;
}