結果

問題 No.5007 Steiner Space Travel
ユーザー unsreunsre
提出日時 2022-07-30 15:04:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 956 ms / 1,000 ms
コード長 7,924 bytes
コンパイル時間 1,549 ms
実行使用メモリ 6,952 KB
スコア 6,947,861
最終ジャッジ日時 2022-07-30 15:05:10
合計ジャッジ時間 33,026 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>
#include <limits>
#include <chrono>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T> using V = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

//constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
//constexpr int INF = numeric_limits<int>::max()/2;
//constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}
long double sqrt(int v) {return sqrt((long double)v);}
long double sqrt(long long v) {return sqrt((long double)v);}

constexpr double baseTimeLimit = 0.95;
#ifdef LOCAL
constexpr int timemul = 1;
#else
constexpr int timemul = 1;
#endif
constexpr double timeLimit = baseTimeLimit * timemul;

constexpr int alpha = 5;

double diff(const chrono::system_clock::time_point &st) {
    return chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now() - st).count() * 1e-6;
}

unsigned int xor96(void) {
  static unsigned int x = 123456789;
  static unsigned int y = 362436069;
  static unsigned int z = 521288629;
  unsigned int t;

  t = (x ^ (x << 3)) ^ (y ^ (y >> 19)) ^ (z ^ (z << 6));
  x = y; y = z;
  return z = t;
}

class State {
public:
    LL score;
    // VLL scores;
    int m;
    VI c,d;
    VI usedCnt;

    State(const State&) = default;
    State(State&&) = default;
    State& operator=(const State&) = default;
    State& operator=(State&&) = default;
    State(int m): score(0), m(m), c(m), d(m), usedCnt(m) {
        REP(i,0,m) {
            c[i] = xor96() % 1001;
            d[i] = xor96() % 1001;
        }
    }
    void init(int n, const VI &a, const VI &b) {
        score = calcScore(n,a,b);
    }
    LL calcScore(int n, const VI &a, const VI &b) {
        LL score = 0;
        REP(i,0,m) usedCnt[i] = 0;

        VI visited(n);
        int idx = 0, cnt = 0;
        while (cnt < n) {
            ++cnt;
            visited[idx] = true;
            int dst = -1;
            LL d = 1LL<<60;
            REP(i,0,n) {
                if (visited[i]) continue;
                if (chmin(d, calcShortest(a[idx],b[idx],a[i],b[i]))) {
                    dst = i;
                }
            }
            if (dst > -1) idx = dst;
        }
        score += calcShortest(a[idx],b[idx],a[0],b[0]);

        return score;
    }

    State modify(int n, const VI &a, const VI &b) {
        // 選択・分岐処理
        int r = xor96() % 2;
        int idx = xor96() % m;
        VI unused;
        REP(i,0,m) if (usedCnt[i] == 0) unused.push_back(i);
        if (!unused.empty()) {
            idx = unused[xor96()%unused.size()];
        }

        State newState(*this);
        if (r % 2) newState.modifyX(n,a,b,idx);
        else newState.modifyY(n,a,b,idx);

        return newState;
    }

    void print(int n, const VI &a, const VI &b) {
        REP(i,0,m) {
            cout << c[i] << " " << d[i] << endl;
        }
        VI visited(n);
        int idx = 0, cnt = 0;
        VI path;
        while (cnt < n) {
            ++cnt;
            visited[idx] = true;
            path.push_back(idx);
            int dst = -1;
            LL d = 1LL<<60;
            REP(i,0,n) {
                if (visited[i]) continue;
                if (chmin(d, calcShortest(a[idx],b[idx],a[i],b[i]))) {
                    dst = i;
                }
            }
            if (dst > -1) idx = dst;
        }

        path.push_back(0);
        VP ps = {{1,0}};
        REP(i,1,path.size()) {
            int sx = a[path[i-1]], sy = b[path[i-1]];
            int tx = a[path[i]], ty = b[path[i]];
            int mid = -1;
            long long ret = 1LL * (sqr(sx-tx) + sqr(sy-ty)) * sqr(alpha);
            REP(i,0,m) {
                int mx = c[i], my = d[i];
                if (chmin(ret, 1LL * (sqr(sx-mx) + sqr(sy-my) + sqr(tx-mx) + sqr(ty-my)) * alpha)) {
                    mid = i;
                }
            }
            if (mid > -1) {
                ps.pb(2,mid);
            }
            ps.pb(1,path[i]);
        }

        cout << ps.size() << endl;
        for (auto [t,r]: ps) {
            cout << t << " " << r + 1 << endl;
        }
    }

private:
    long long calcShortest(int sx, int sy, int tx, int ty) {
        long long ret = 1LL * (sqr(sx-tx) + sqr(sy-ty)) * sqr(alpha);
        int mid = -1;
        REP(i,0,m) {
            int mx = c[i], my = d[i];
            if (chmin(ret, 1LL * (sqr(sx-mx) + sqr(sy-my) + sqr(tx-mx) + sqr(ty-my)) * alpha)) {
                mid = i;
            }
        }
        if (mid > -1) usedCnt[mid]++;

        return ret;
    }

    void modifyX(int n, const VI &a, const VI &b, int idx) {
        int dist = xor96() % 1000 - 500;
        c[idx] = max(0,min(1000,c[idx]+dist));
        score = calcScore(n,a,b);
    }
    void modifyY(int n, const VI &a, const VI &b, int idx) {
        int dist = xor96() % 1000 - 500;
        d[idx] = max(0,min(1000,d[idx]+dist));
        score = calcScore(n,a,b);
    }
};

// 焼きなまし法
State sa(int n, int m, const VI &a, const VI &b, double start_temp, double end_temp, double TIME_LIMIT) {
    State state(m);
    state.init(n,a,b);

    //int times = 0;
    chrono::system_clock::time_point st = chrono::system_clock::now();

    int cnt = 0;
    double dt;
    while ((dt = diff(st)) < TIME_LIMIT) { // 時間の許す限り回す
        REP(loop,0,10) {
            State new_state = state.modify(n,a,b);
            int new_score = new_state.score;
            int pre_score = state.score;

            // 温度関数
            double temp = start_temp + (end_temp - start_temp) * dt / TIME_LIMIT;
            // 遷移確率関数
            double prob = exp(-((double)(new_score-pre_score))/temp); // 最小値
            // double prob = exp(((double)(new_score-pre_score))/temp); // 最大値
            if (prob > (xor96()%0xffffffffu)/(double)0xffffffffu) { // 確率probで遷移する
                state = new_state;
            }
        }
        ++cnt;
        dump(state.score);
    }
    dump(cnt);

    return state;
}

void solve() {
    auto st = chrono::system_clock::now();

    int r = random_device()() % 1000;
    REP(i,0,r) xor96();

    int n,m;
    cin >> n >> m;
    VI a(n),b(n);
    REP(i,0,n) cin >> a[i] >> b[i];

    int times = 2;
    auto state = sa(n,m,a,b,1000,100,timeLimit/times);
    REP(i,1,times) {
        auto state2 = sa(n,m,a,b,1000,100,timeLimit/times);
        if (state2.score < state.score) {
            state = move(state2);
        }
    }
    dump(state.score);

    state.print(n,a,b);
}

signed main() {
    int t = 1;
    // cin >> t;
    REP(i,0,t) {
        solve();
    }
    
    return 0;
}
0