結果

問題 No.5007 Steiner Space Travel
ユーザー tabae326tabae326
提出日時 2023-04-24 21:44:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 805 ms / 1,000 ms
コード長 15,210 bytes
コンパイル時間 5,831 ms
コンパイル使用メモリ 286,948 KB
実行使用メモリ 4,372 KB
スコア 7,799,831
最終ジャッジ日時 2023-04-24 21:44:58
合計ジャッジ時間 32,462 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 804 ms
4,368 KB
testcase_01 AC 804 ms
4,368 KB
testcase_02 AC 803 ms
4,368 KB
testcase_03 AC 803 ms
4,368 KB
testcase_04 AC 804 ms
4,368 KB
testcase_05 AC 804 ms
4,372 KB
testcase_06 AC 804 ms
4,372 KB
testcase_07 AC 804 ms
4,368 KB
testcase_08 AC 804 ms
4,372 KB
testcase_09 AC 804 ms
4,372 KB
testcase_10 AC 804 ms
4,372 KB
testcase_11 AC 804 ms
4,372 KB
testcase_12 AC 804 ms
4,368 KB
testcase_13 AC 804 ms
4,372 KB
testcase_14 AC 803 ms
4,372 KB
testcase_15 AC 803 ms
4,372 KB
testcase_16 AC 804 ms
4,372 KB
testcase_17 AC 804 ms
4,372 KB
testcase_18 AC 804 ms
4,372 KB
testcase_19 AC 804 ms
4,368 KB
testcase_20 AC 804 ms
4,368 KB
testcase_21 AC 804 ms
4,368 KB
testcase_22 AC 804 ms
4,372 KB
testcase_23 AC 804 ms
4,372 KB
testcase_24 AC 804 ms
4,368 KB
testcase_25 AC 804 ms
4,368 KB
testcase_26 AC 803 ms
4,372 KB
testcase_27 AC 804 ms
4,368 KB
testcase_28 AC 803 ms
4,368 KB
testcase_29 AC 805 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <sys/time.h>
#include <atcoder/all>
using namespace std;
#pragma region prototype_declaration
/* ==============================================
============================================== */
/**/
struct RandGenerator {
random_device seed_gen;
mt19937 engine;
mt19937_64 engine64;
static const int pshift = 1000000000;
RandGenerator() : engine(seed_gen()), engine64(seed_gen()) {}
/*mod32bit*/
int rand(int mod) {
return engine() % mod;
}
/*mod64bit*/
long long randll(long long mod) {
return engine64() % mod;
}
/*pTrue*/
bool pjudge(double p) {
int p_int;
if(p > 1) p_int = pshift;
else p_int = p * pshift;
return rand(pshift) < p_int;
}
} ryuka;
/**/
struct Timer {
double global_start;
/**/
double gettime() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
void init() {
global_start = gettime();
}
/**/
double elapsed() {
return gettime() - global_start;
}
} toki;
struct Node {
enum Type {
planet,
station
};
int x, y, id, to, from;
Type type;
Node() : to(-1), from(-1) {};
Node(int, int, int, Type);
};
struct Input {
/*TODO: */
int n, m;
const int a = 5;
vector<Node> planets;
void read();
} input;
struct Output {
/*TODO: */
vector<Node> stations;
vector<Node> route;
Output();
void print();
};
/**/
struct State {
Output output;
long long length;
long long score;
State() : score(0) {}
static State initState();
static State generateState(const State& input_state);
};
/**/
template<class STATE>
struct IterationControl {
int iteration_counter;
int swap_counter;
double average_time;
double start_time;
IterationControl() : iteration_counter(0), swap_counter(0) {}
/**/
STATE climb(double time_limit, STATE initial_state) {
start_time = toki.gettime();
average_time = 0;
STATE best_state = initial_state;
double time_stamp = start_time;
cerr << "[INFO] - IterationControl::climb - Starts climbing...\n";
while(time_stamp - start_time + average_time < time_limit) {
STATE current_state = STATE::generateState(best_state);
if(current_state.score > best_state.score) {
swap(best_state, current_state);
swap_counter++;
}
iteration_counter++;
time_stamp = toki.gettime();
average_time = (time_stamp - start_time) / iteration_counter;
}
cerr << "[INFO] - IterationControl::climb - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
return best_state;
}
/**/
STATE anneal(double time_limit, double temp_start, double temp_end, STATE initial_state) {
assert(temp_start >= temp_end);
start_time = toki.gettime();
average_time = 0;
STATE best_state = initial_state;
double elapsed_time = 0;
cerr << "[INFO] - IterationControl::anneal - Starts annealing...\n";
while(elapsed_time + average_time < time_limit) {
double normalized_time = elapsed_time / time_limit;
double temp_current = pow(temp_start, 1.0 - normalized_time) * pow(temp_end, normalized_time);
STATE current_state = STATE::generateState(best_state);
long long delta = current_state.score - best_state.score;
if(delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current)) ) {
swap(best_state, current_state);
swap_counter++;
}
iteration_counter++;
elapsed_time = toki.gettime() - start_time;
average_time = elapsed_time / iteration_counter;
}
cerr << "[INFO] - IterationControl::anneal - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
return best_state;
}
};
namespace Utils {
int calcSquareDist(const Node& a, const Node& b);
bool isPlanet(const Node& node);
bool isStart(const Node& node);
pair<long long, long long> calcScore(const Output& output);
long long calcScoreFromLength(long long length);
vector<Node> initStations();
vector<Node> solveInsertedTSP(const vector<Node>& stations);
vector<Node> insertStations(const vector<Node>& nodes);
pair<vector<Node>, vector<Node>> goThroughStations(const vector<Node>& nodes);
vector<Node> rearrangeRoute(const vector<Node>& nodes);
};
/* ==============================================
============================================== */
#pragma endregion prototype_declaration
Node::Node(int x, int y, int id, Node::Type type) :
x(x), y(y), id(id), type(type) {
;
}
/*TODO: */
void Input::read() {
cin >> n >> m;
planets.resize(n);
for(int i = 0; i < n; i++) {
cin >> planets[i].x >> planets[i].y;
planets[i].id = i;
planets[i].type = Node::Type::planet;
}
}
/*TODOvector*/
Output::Output() {
}
/*TODO*/
void Output::print() {
assert(stations.size() == input.m);
for(auto e : stations) {
cout << e.x << " " << e.y << endl;
}
cout << route.size() << endl;
for(auto e : route) {
cout << (Utils::isPlanet(e) ? 1 : 2) << " " << e.id + 1 << endl;
}
}
/*TODO: */
State State::initState() {
State res;
res.output.route = Utils::solveInsertedTSP(vector<Node>());
auto [score, length] = Utils::calcScore(res.output);
res.score = score;
res.length = length;
return res;
}
/*TODO: input_state*/
State State::generateState(const State& input_state) {
State res = input_state;
int i = ryuka.rand(res.output.route.size());
int j = ryuka.rand(res.output.route.size());
int i2 = res.output.route[i].to;
int j2 = res.output.route[j].to;
bool chk = (i != j) && (i != j2) && (j != i2);
if(chk) {
res.length -= input.a * input.a * Utils::calcSquareDist(res.output.route[i], res.output.route[i2]);
res.length -= input.a * input.a * Utils::calcSquareDist(res.output.route[j], res.output.route[j2]);
res.length += input.a * input.a * Utils::calcSquareDist(res.output.route[i], res.output.route[j]);
res.length += input.a * input.a * Utils::calcSquareDist(res.output.route[j2], res.output.route[i2]);
res.output.route[i].to = j;
res.output.route[j2].from = i2;
int cur = j;
while(true) {
int nxt = res.output.route[cur].from;
swap(res.output.route[cur].from, res.output.route[cur].to);
if(cur == j) res.output.route[cur].from = i;
if(cur == i2) {
res.output.route[cur].to = j2;
break;
}
cur = nxt;
}
res.score = Utils::calcScoreFromLength(res.length);
}
return res;
}
int Utils::calcSquareDist(const Node& a, const Node& b) {
const int dx = a.x - b.x;
const int dy = a.y - b.y;
return dx * dx + dy * dy;
}
bool Utils::isStart(const Node& node) {
return isPlanet(node) && node.id == 0;
}
bool Utils::isPlanet(const Node& node) {
return node.type == Node::Type::planet;
}
/*TODO: */
pair<long long, long long> Utils::calcScore(const Output& output) {
long long sum = 0;
const auto& route = output.route;
int debug = 0;
Node cur = route.front();
assert(Utils::isStart(cur));
while(true) {
Node nxt = route[cur.to];
const long long d2 = Utils::calcSquareDist(cur, nxt);
if(isPlanet(cur) && isPlanet(nxt)) {
sum += input.a * input.a * d2;
} else if(!isPlanet(cur) && !isPlanet(nxt)) {
sum += d2;
} else {
debug++;
sum += input.a * d2;
}
cur = nxt;
if(Utils::isStart(cur)) break;
}
long long res = (long long)(1e9 / (1e3 + sqrt(sum)));
return {res, sum};
}
long long Utils::calcScoreFromLength(long long length) {
long long res = (long long)(1e9 / (1e3 + sqrt(length)));
return res;
}
vector<Node> Utils::rearrangeRoute(const vector<Node>& route) {
vector<Node> res;
Node cur = route.front();
while(true) {
Node nxt = route[cur.to];
res.push_back(cur);
if(Utils::isStart(nxt)) {
res.push_back(nxt);
break;
}
cur = nxt;
}
return res;
}
vector<Node> Utils::solveInsertedTSP(const vector<Node>& stations) {
vector<Node> nodes, route;
for(auto e: input.planets) if(e.id != 0) nodes.push_back(e);
for(auto e: stations) nodes.push_back(e);
route.push_back(input.planets.front());
route.push_back(input.planets.front());
shuffle(route.begin(), route.end(), ryuka.engine);
for(auto e: nodes) {
int min_dist = 1<<30, min_id = -1;
for(int i = 0; i < route.size() - 1; i++) {
int dist = Utils::calcSquareDist(e, route[i]) + Utils::calcSquareDist(e, route[i+1]);
if(min_dist > dist) {
min_dist = dist;
min_id = i + 1;
}
}
assert(min_id != -1);
route.insert(route.begin() + min_id, e);
}
for(int i = 0; i < route.size() - 2; i++) route[i].to = i+1;
for(int i = 1; i < route.size() - 1; i++) route[i].from = i-1;
route[route.size()-2].to = 0;
route[0].from = route.size() - 2;
route.pop_back();
return route;
}
vector<Node> Utils::insertStations(const vector<Node>& nodes) {
vector<pair<int, int>> v;
vector<Node> res = nodes;
for(int i = 0; i < res.size(); i++) {
v.push_back({Utils::calcSquareDist(res[i], res[res[i].to]), i});
}
sort(v.begin(), v.end(), greater<pair<int,int>>());
sort(v.begin(), v.begin() + min<int>(input.m, v.size()), [](auto l, auto r) {
return l.second < r.second;
});
vector<pair<int, Node>> inserted;
for(auto [_, i]: v) {
int nx = min(res[i].x, res[res[i].to].x) + abs(res[i].x - res[res[i].to].x) / 2;
int ny = min(res[i].y, res[res[i].to].y) + abs(res[i].y - res[res[i].to].y) / 2;
inserted.push_back({i, Node(nx, ny, inserted.size(), Node::Type::station)});
if(inserted.size() == input.m) break;
}
for(auto [i, node]: inserted) {
int ri = res.size();
node.to = res[i].to;
res[i].to = ri;
res.push_back(node);
}
return res;
}
vector<Node> Utils::initStations() {
vector<int> cluster(input.n, 0);
for(int i = 0; i < input.n; i++) {
cluster[i] = i % input.m;
}
vector<int> prev;
int count = 0;
const int iter_max = 1000;
while(prev != cluster && count < iter_max) {
vector<long long> w_x(input.m, 0);
vector<long long> w_y(input.m, 0);
vector<int> num(input.m, 0);
for(int i = 0; i < input.n; i++) {
w_x[cluster[i]] += input.planets[i].x;
w_y[cluster[i]] += input.planets[i].y;
num[cluster[i]]++;
}
for(int i = 0; i < input.m; i++) {
if(num[i] > 0) {
w_x[i] /= num[i];
w_y[i] /= num[i];
}
}
for(int i = 0; i < input.n; i++) {
int min_dist = 1<<30, min_id = -1;
for(int j = 0; j < input.m; j++) {
int dist = Utils::calcSquareDist(input.planets[i], Node(w_x[j], w_y[j], -1, Node::Type::station));
if(dist < min_dist) {
min_dist = dist;
min_id = j;
}
}
assert(min_id != -1);
cluster[i] = min_id;
}
count++;
}
if(count >= iter_max) {
cerr << "[WARNING] - Utils::initStations - Failed to k-means" << endl;
/*
for(int i = 0; i < input.n; i++) {
cerr << cluster[i] << " " << input.planets[i].x << " " << input.planets[i].y << endl;
}
*/
}
vector<Node> res(input.m);
vector<long long> w_x(input.m, 0);
vector<long long> w_y(input.m, 0);
vector<int> num(input.m, 0);
for(int i = 0; i < input.n; i++) {
w_x[cluster[i]] += input.planets[i].x;
w_y[cluster[i]] += input.planets[i].y;
num[cluster[i]]++;
}
for(int i = 0; i < input.m; i++) {
if(num[i] > 0) {
w_x[i] /= num[i];
w_y[i] /= num[i];
}
}
for(int i = 0; i < input.m; i++) {
res[i] = Node(w_x[i], w_y[i], i, Node::Type::station);
}
return res;
}
pair<vector<Node>, vector<Node>> Utils::goThroughStations(const vector<Node>& route) {
vector<Node> res;
vector<Node> stations = Utils::initStations();
Node cur = route.front();
int prev = -1;
while(true) {
Node nxt = route[cur.to];
int cur_pos = res.size();
cur.from = prev;
cur.to = cur_pos + 1;
prev = cur_pos;
res.push_back(cur);
int min_dist = input.a * Utils::calcSquareDist(cur, nxt);
Node min_node;
bool insert = false;
for(auto st: stations) {
int dist = Utils::calcSquareDist(cur, st) + Utils::calcSquareDist(st, nxt);
if(dist < min_dist) {
min_dist = dist;
min_node = st;
insert = true;
}
}
if(insert) {
cur.to = min_node.id;
int cur_pos = res.size();
prev = cur_pos;
min_node.from = cur_pos - 1;
min_node.to = cur_pos + 1;
res.push_back(min_node);
}
if(Utils::isStart(nxt)) {
res[0].from = res.size() - 1;
res[res.size()-1].to = 0;
break;
}
cur = nxt;
}
return {res, stations};
}
int main(int argc, char* argv[]) {
toki.init();
input.read();
IterationControl<State> sera;
State ans = sera.anneal(0.8, 1e5, 50, State::initState());
//State ans = sera.climb(0.8, State::initState());
//State ans = State::initState();
auto [route, stations] = Utils::goThroughStations(ans.output.route);
ans.output.route = route;
ans.output.stations = stations;
ans.score = Utils::calcScore(ans.output).first;
ans.output.route = Utils::rearrangeRoute(ans.output.route);
ans.output.print();
cerr << "[INFO] - main - MyScore = " << ans.score << "\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0