結果

問題 No.5007 Steiner Space Travel
ユーザー olpheolphe
提出日時 2022-07-30 17:07:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 884 ms / 1,000 ms
コード長 4,358 bytes
コンパイル時間 1,580 ms
実行使用メモリ 6,952 KB
スコア 8,573,588
最終ジャッジ日時 2022-07-30 17:08:11
合計ジャッジ時間 29,918 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 839 ms
6,948 KB
testcase_01 AC 853 ms
4,900 KB
testcase_02 AC 840 ms
4,904 KB
testcase_03 AC 846 ms
6,948 KB
testcase_04 AC 857 ms
6,948 KB
testcase_05 AC 845 ms
4,908 KB
testcase_06 AC 875 ms
4,904 KB
testcase_07 AC 838 ms
6,948 KB
testcase_08 AC 867 ms
4,908 KB
testcase_09 AC 816 ms
4,900 KB
testcase_10 AC 823 ms
4,904 KB
testcase_11 AC 849 ms
6,948 KB
testcase_12 AC 817 ms
4,904 KB
testcase_13 AC 836 ms
6,952 KB
testcase_14 AC 828 ms
4,904 KB
testcase_15 AC 849 ms
4,900 KB
testcase_16 AC 821 ms
6,952 KB
testcase_17 AC 844 ms
4,900 KB
testcase_18 AC 838 ms
6,948 KB
testcase_19 AC 845 ms
4,904 KB
testcase_20 AC 850 ms
4,900 KB
testcase_21 AC 819 ms
4,904 KB
testcase_22 AC 837 ms
4,904 KB
testcase_23 AC 855 ms
4,904 KB
testcase_24 AC 838 ms
4,900 KB
testcase_25 AC 851 ms
4,904 KB
testcase_26 AC 833 ms
5,160 KB
testcase_27 AC 817 ms
6,948 KB
testcase_28 AC 841 ms
6,948 KB
testcase_29 AC 884 ms
6,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr int by = 5;

int N, M;
vector<int>x;
vector<int>y;
vector<int>ans;

class XorShift {
	unsigned int x, y, z, w, t;
public:
	XorShift() {
		x = 133553533;
		y = 314867339;
		z = 664298413;
		w = 999999937;
		t = 0;
	}
	unsigned int rand() {
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w & 0x7fffffff;
	}
};

XorShift xs;

void Initialize() {
	cin >> N >> M;
	x.resize(N);
	y.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}

}


int Score(vector<vector<int>>dis, vector<int>route) {
	int sum = 0;
	for (int i = 1; i < route.size(); i++) {
		sum += dis[route[i - 1]][route[i]];
	}
	return round(1e9 / (1000 + sqrt(sum)));
}

int Dist(int x1, int x2, int y1, int y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

void Station() {
	vector<int>cl(N);
	for (int i = 0; i < N; i++) {
		cl[i] = xs.rand() % M;
	}
	vector<double>cx(M);
	vector<double>cy(M);
	for (int i = 0; i < 100; i++) {
		for (auto& i : cx)i = 0;
		for (auto& i : cy)i = 0;
		vector<int>cnum(M);
		for (int i = 0; i < N; i++) {
			cx[cl[i]] += x[i];
			cy[cl[i]] += y[i];
			cnum[cl[i]]++;
		}
		for (int i = 0; i < M; i++) {
			if (cnum[i]) {
				cx[i] /= cnum[i];
				cy[i] /= cnum[i];
			}
		}
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (Dist(x[j], cx[cl[j]], y[j], cy[cl[j]]) > Dist(x[j], cx[k], y[j], cy[k])) {
					cl[j] = k;
				}
			}
		}
	}
	for (int i = 0; i < M; i++) {
		x.push_back(round(cx[i]));
		y.push_back(round(cy[i]));
	}
}

int bestscore = 0;
vector<int>outx;
vector<int>outy;

void TSP() {
	vector<vector<int>>dis(N, vector<int>(N));
	vector<vector<vector<int>>>use(N, vector<vector<int>>(N));
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			dis[j][i] = dis[i][j] = Dist(x[i], x[j], y[i], y[j]) * by * by;
			for (int k = 0; k < M; k++) {
				for (int l = 0; l < M; l++) {
					int c = Dist(x[i], x[N + k], y[i], y[N + k]) * by + Dist(x[N + k], x[N + l], y[N + k], y[N + l]) + Dist(x[N + l], x[j], y[N + l], y[j]) * by;
					if (c < dis[i][j]) {
						dis[i][j] = c;
						use[i][j] = { N + k,N + l };
						use[j][i] = { N + l,N + k };
						dis[j][i] = c;
					}
				}
			}
		}
	}
	vector<int>route(N + 1);
	for (int i = 0; i < N + 1; i++) {
		route[i] = i % N;
	}
	double startTemp = 50000;
	double endTemp = 1;
	int LOOP = 100000;
	for (int loop = 0; loop < LOOP; loop++) {
		int a = xs.rand() % (N - 1);
		int b = xs.rand() % (N - 2) + a + 1;
		b %= N - 1;
		if (a > b)swap(a, b);
		a++;
		b += 2;
		int bef = dis[route[a - 1]][route[a]] + dis[route[b - 1]][route[b]];
		int aft = dis[route[a - 1]][route[b - 1]] + dis[route[a]][route[b]];
		int dif = bef - aft;
		double temp = startTemp + (endTemp - startTemp) * loop / LOOP;
		double probability = exp((bef - aft) / temp);
		bool FORCE_NEXT = probability > ((double)(xs.rand() % 10000000) / 10000000);
		if (FORCE_NEXT) {
			reverse(route.begin() + a, route.begin() + b);
		}
		else {

		}
	}
	int score = Score(dis, route);
	cerr << score << endl;
	if (bestscore < score) {
		bestscore = score;
		ans.clear();
		outx.clear();
		outy.clear();
		for (int i = N; i < x.size(); i++) {
			outx.push_back(x[i]);
			outy.push_back(y[i]);
		}
		ans.push_back(route[0]);
		for (int i = 0; i < N; i++) {
			if (use[route[i]][route[i + 1]].size()) {
				ans.push_back(use[route[i]][route[i + 1]][0]);
				ans.push_back(use[route[i]][route[i + 1]][1]);
			}
			ans.push_back(route[i + 1]);
		}
	}
}

void Output() {
	cerr << "----------------" << endl;
	for (int i = 0; i < outx.size(); i++) {
		cout << outx[i] << " " << outy[i] << endl;
	}
	cout << ans.size() << endl;
	for (auto i : ans) {
		if (i < N) {
			cout << 1 << " " << i + 1 << endl;
		}
		else {
			cout << 2 << " " << i - N + 1 << endl;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	Initialize();
	for (int i = 0; i < 100; i++) {
		Station();
		TSP();
		x.resize(N);
		y.resize(N);
	}
	Output();
}
0