結果
問題 | No.5007 Steiner Space Travel |
ユーザー | tabae326 |
提出日時 | 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 |
ソースコード
#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()) {}/*mod以下の乱数を返す(32bit)*/int rand(int mod) {return engine() % mod;}/*mod以下の乱数を返す(64bit)*/long long randll(long long mod) {return engine64() % mod;}/*確率pでTrueを返す*/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_declarationNode::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;}}/*TODO:ここで出力変数を初期化する。vectorのメモリ確保など*/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";}