結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 15:03:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 1,000 ms |
コード長 | 9,935 bytes |
コンパイル時間 | 1,746 ms |
実行使用メモリ | 5,164 KB |
スコア | 6,916,319 |
最終ジャッジ日時 | 2022-07-30 15:03:55 |
合計ジャッジ時間 | 3,843 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))#define ALL(x) std::begin(x), std::end(x)// Debugtemplate<class T>void print_collection(std::ostream& out, T const& x);template<class A>std::ostream& operator<<(std::ostream& out, std::vector<A> const& x) { print_collection(out, x); return out; }template<class A, size_t N>std::ostream& operator<<(std::ostream& out, std::array<A, N> const& x) { print_collection(out, x); return out; }template<class T, size_t... I>void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>);template<class... A>std::ostream& operator<<(std::ostream& out, std::tuple<A...> const& x) {print_tuple(out, x, std::index_sequence_for<A...>{});return out;}template<class T, size_t... I>void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>){using swallow = int[];out << '(';(void)swallow{0, (void(out << (I == 0? "" : ", ") << std::get<I>(a)), 0)...};out << ')';}template<class T>void print_collection(std::ostream& out, T const& x) {int f = 0;out << '[';for(auto const& i: x) {out << (f++ ? "," : "");out << i;}out << "]";}static inline void d1_impl_seq() { std::cerr << "}"; }template <class T, class... V>void d1_impl_seq(T const& t, V const&... v) {std::cerr << t;if(sizeof...(v)) { std::cerr << ", "; }d1_impl_seq(v...);}static inline void d2_impl_seq() { }template <class T, class... V>void d2_impl_seq(T const& t, V const&... v) {std::cerr << " " << t;d2_impl_seq(v...);}#define D0(x) do { std::cerr << __FILE__ ":" << __LINE__ << ":" << __func__ << " " << x << std::endl; } while (0)#define D1(x...) do { \std::cerr << __LINE__ << " {" << #x << "} = {"; \d1_impl_seq(x); \std::cerr << std::endl << std::flush; \} while(0)#define D2(x...) do { \std::cerr << "!"; \d2_impl_seq(x); \std::cerr << std::endl << std::flush; \} while(0)using namespace std;static constexpr int INF = 1<<30;// #define NDEBUGstatic std::vector<std::string> split(const std::string &s, char delim) {std::vector<std::string> elems;std::stringstream ss(s);std::string item;while (getline(ss, item, delim)) {if (!item.empty()) {elems.push_back(item);}}return elems;}struct XorShift {unsigned int x, y, z, w;double nL[65536];XorShift() { init(); }void init(){x = 314159265; y = 358979323; z = 846264338; w = 327950288;double n = 1 / (double)(2 * 65536);for (int i = 0; i < 65536; i++) {nL[i] = log(((double)i / 65536) + n);}}inline unsigned int next() { unsigned int t=x^x<<11; x=y; y=z; z=w; return w=w^w>>19^t^t>>8; }inline double nextLog() { return nL[next()&0xFFFF]; }inline int nextInt(int m) { return (int)(next()%m); } // [0, m)int nextInt(int min, int max) { return min+nextInt(max-min+1); } // [min, max]inline double nextDouble() { return (double)next()/((long long)1<<32); } // [0, 1]};XorShift rng;template <typename T>inline void rough_shuffle(vector<T>& lv) {int n = lv.size();for (int i = n; i > 0; --i) {int id = rng.nextInt(i);swap(lv[id], lv[i-1]);}}std::size_t calc_hash(std::vector<int> const& vec) {std::size_t seed = vec.size();for(auto& i : vec) {seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);}return seed;}struct Timer {const double LIMIT; // FIXME: 時間制限(s)Timer() : LIMIT(0.95) { reset(); }Timer(double limit) : LIMIT(limit) { reset(); }chrono::system_clock::time_point start;void reset() {start = chrono::system_clock::now();}double get() {auto end = chrono::system_clock::now();return chrono::duration_cast<chrono::milliseconds>(end - start).count()/1000.0;}};// ------------- Constants ------------constexpr int N = 100;constexpr int M = 8;constexpr int A = 5; // alphaconstexpr int AA = 25; // alpha*alphaint dist_[N][N];struct Pos {int x = -1, y = -1, c = -1;Pos() {}Pos(int x, int y): x(x), y(y) {}bool operator == (const Pos &other) const {return (other.x == x) && (other.y == y);}bool operator != (const Pos &other) const {return !((*this) == other);}int distance(const Pos &other) const {return (x-other.x)*(x-other.x)+(y-other.y)*(y-other.y);}int id2() const { return y*N+x; }friend std::ostream& operator<<(std::ostream& os, const Pos &p) {os << "(" << p.x << "," << p.y << ")";return os;}};Pos ps[N];vector<Pos> cps(M);vector<int> bestRoute; // cpsのめぐる順Pos calcCenter(int cid) {int sx = 0, sy = 0;int n = 0;REP(i,N) {if (ps[i].c != cid) continue;sx += ps[i].x;sy += ps[i].y;++n;}if (n == 0) return Pos(rng.nextInt(1000), rng.nextInt(1000));assert(n > 0);return Pos(sx/n, sy/n);}void kmeans() {// initREP(i,N) {ps[i].c = rng.nextInt(M);}REP(t,100) {// calc centerREP(i,M) {cps[i] = calcCenter(i);}D1(cps);// assign centerREP(i,N) {int bj = -1;int best = INF;REP(j,M) {int d = ps[i].distance(cps[j]);if (d < best) {bj = j;best = d;}}assert(bj != -1);ps[i].c = bj;}}}// center同士の訪れ方vector<bool> visit(M);int bestRouteScore = INF;void dfs(int cur, int sumd, vector<int> &route) {if (route.size() == M) {int d = cps[route[M-1]].distance(cps[route[0]]);int score = sumd+d;if (score < bestRouteScore) {bestRoute = route;bestRouteScore = score;}return;}visit[cur] = true;REP(i,M) {if (visit[i]) continue;int d = cps[cur].distance(cps[i]);route.push_back(i);dfs(i, sumd+d, route);route.pop_back();}visit[cur] = false;}struct State {double score = 0;int btype = 0;State(){}double update(double progress) {return 0;}int calcScore() {int ret = 0;return ret;}void revert() {// if (btype == 1) revert1();// else if (btype == 2) revert2();// else if (btype == 3) revert3();}void revert1() {}void write() {REP(i,M) {cout << cps[i].x << " " << cps[i].y << endl;}vector<pair<int,int>> out;REP(i,M) {int c = bestRoute[i];if (i > 0) out.emplace_back(2, c+1);if (i == 0) {assert(ps[0].c == c);}REP(j,N) {if (ps[j].c != c) continue;out.emplace_back(1, j+1);out.emplace_back(2, c+1);}}out.emplace_back(1, 1);cout << out.size() << endl;for (auto it: out) {cout << it.first << " " << it.second << endl;}} // write current solution};void initState(State &s) {s.score = s.calcScore();}struct SASolver {double startTemp = 3;double endTemp = 0.001;// Timer timer = Timer(2.85);Timer timer = Timer(0.85);// Timer timer = Timer(200);State best;SASolver() { init(); }SASolver(double st, double et): startTemp(st), endTemp(et) { init(); }SASolver(double st, double et, double limit): startTemp(st), endTemp(et), timer(limit) { init(); }void init() {} // 初期化処理をここに書くvoid solve(State &state) {double t;best = state;int step = 0;vector<int> total(6);vector<int> ac(6);// best.write();while ((t = timer.get()) < timer.LIMIT) // 焼きなまし終了時刻までループ{double T = startTemp + (endTemp - startTemp) * t / timer.LIMIT;double progress = t/timer.LIMIT;// assert(0 <= progress && progress <= 1);for (int i = 0; i < 100; ++i) { // 時間計算を間引くdouble diff = state.update(progress);total[state.btype]++;if (diff <= -INF+0.1) {state.revert();continue;}// 最初t=0のときは、スコアが良くなろうが悪くなろうが、常に次状態を使用// 最後t=timer.LIMITのときは、スコアが改善したときのみ、次状態を使用// スコアが良くなった or 悪くなっても強制遷移double tr = T*rng.nextLog();// cerr << t << " " << T << " " << tr << " " << diff << endl;if (diff >= tr){ac[state.btype]++;if (best.score < state.score) {best = state;// D1(t, step, best.score);// best.write();}}else { state.revert(); }++step;}}D1(step, best.score);REP3(i,1,6) {if (total[i] == 0) continue;cerr << i << ":" << 1.0*ac[i]/total[i] << "(" << ac[i] << "/" << total[i] << ")" << endl;}}};struct Solver {Solver() {reset();}void reset() {}void solve() {State state; // 開始状態initState(state);vector<int> route = {ps[0].c};dfs(ps[0].c, 0, route);D1(bestRouteScore, bestRoute);state.write();// SASolver s;// s.solve(state);// s.best.write();// show(s.best.grid);// float score = s.best.calcScore();// D1(score);}void readInput() {int n_, m_;cin >> n_ >> m_;REP(i,N) {int x, y; cin >> x >> y;ps[i] = Pos(x,y);}}};void initPos() {REP(i,N) REP(j,N) dist_[i][j] = ps[i].distance(ps[j]);}int main(){Solver solver;solver.readInput();initPos();kmeans();solver.solve();}