#785956 (C++14) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	rinrion
提出日時	2022-08-07 16:08:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,349 bytes
コンパイル時間	3,313 ms
実行使用メモリ	6,952 KB
スコア	4,360,994
最終ジャッジ日時	2022-08-07 16:08:57
合計ジャッジ時間	35,188 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	991 ms 4,900 KB
testcase_01	TLE	-
testcase_02	AC	996 ms 4,604 KB
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	AC	983 ms 6,952 KB
testcase_07	AC	997 ms 4,604 KB
testcase_08	AC	997 ms 4,500 KB
testcase_09	TLE	-
testcase_10	AC	994 ms 6,948 KB
testcase_11	AC	993 ms 4,596 KB
testcase_12	AC	985 ms 4,392 KB
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	992 ms 4,532 KB
testcase_16	AC	991 ms 4,716 KB
testcase_17	AC	990 ms 6,948 KB
testcase_18	AC	995 ms 6,952 KB
testcase_19	AC	992 ms 4,428 KB
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	AC	985 ms 4,548 KB
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	AC	992 ms 6,952 KB
testcase_29	AC	994 ms 6,948 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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=450,timelmt_2=980;
double gettime;
chrono::system_clock::time_point  time_now;
chrono::system_clock::time_point  time_start = chrono::system_clock::now(); 

double start_temp=500, 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;
	int cnt2=0,cnt2_rec;

	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+(end_temp-start_temp)*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();

		bool judge=false;
		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){
//	for(int q=0; q<100; q++){
		if((int)cnt2%5000==0){
			time_now = chrono::system_clock::now(); 
			gettime = chrono::duration_cast<chrono::milliseconds>(time_now-time_start).count();
			temp=start_temp+(end_temp-start_temp)*gettime/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を計算しなおす

		if(score_t>score){//山登り
			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||cnt2==0){//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<<" "<<fixed<<setprecision(2)<<(double)cnt2_rec/cnt2<<endl;

}

yukicoder

結果

テストケース

ソースコード