#783057 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	eijirou
提出日時	2022-07-30 16:01:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	8,176 bytes
コンパイル時間	4,116 ms
実行使用メモリ	4,120 KB
スコア	7,056,175
最終ジャッジ日時	2022-07-30 16:01:10
合計ジャッジ時間	5,824 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 3,844 KB
testcase_01	AC	2 ms 3,808 KB
testcase_02	AC	2 ms 4,004 KB
testcase_03	AC	2 ms 3,936 KB
testcase_04	AC	2 ms 3,812 KB
testcase_05	AC	2 ms 3,748 KB
testcase_06	AC	2 ms 3,968 KB
testcase_07	AC	2 ms 4,004 KB
testcase_08	AC	1 ms 4,120 KB
testcase_09	AC	2 ms 3,896 KB
testcase_10	AC	2 ms 3,972 KB
testcase_11	AC	2 ms 3,748 KB
testcase_12	AC	1 ms 4,120 KB
testcase_13	AC	2 ms 3,812 KB
testcase_14	AC	2 ms 3,744 KB
testcase_15	AC	2 ms 4,116 KB
testcase_16	AC	2 ms 3,744 KB
testcase_17	AC	1 ms 3,932 KB
testcase_18	AC	2 ms 3,912 KB
testcase_19	AC	2 ms 3,812 KB
testcase_20	AC	2 ms 3,916 KB
testcase_21	AC	1 ms 3,972 KB
testcase_22	AC	2 ms 3,952 KB
testcase_23	AC	2 ms 4,120 KB
testcase_24	AC	2 ms 3,972 KB
testcase_25	AC	2 ms 3,748 KB
testcase_26	AC	2 ms 3,812 KB
testcase_27	AC	2 ms 3,948 KB
testcase_28	AC	2 ms 3,812 KB
testcase_29	AC	2 ms 3,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

template <class T>
T sum(vector<T>& array) {
    return accumulate(array.begin(), array.end(), (T)0);
}

template <class T>
int index(vector<T>& data, T element) {
    return distance(data.begin(), find(data.begin(),data.end(),element));
}

template <class T>
int contain(vector<T>& data, T element) {
    return !(index(data, element) == (int)data.size());
}

struct Randomizer {
    mt19937_64 engine;
    uniform_int_distribution<> dist = uniform_int_distribution<>(0, INT_MAX);

    Randomizer() {
        random_device seed_gen;
        engine = mt19937_64(seed_gen());
    }

    Randomizer(int seed) {
        engine = mt19937_64(seed);
    }

    double uniform(double l, double r) {
        assert(l <= r);
        return l + (r-l)*dist(engine)/INT_MAX;
    }

    int randrange(int l, int r) {
        assert(l < r);
        return l + dist(engine)%(r-l);
    }

    template <class T>
    T choice(vector<T>& data) {
        return data.at(randrange(0, data.size()));
    }

    vector<int> sample(int l, int r, int num) {
        assert(0 < num && num <= r - l);
        vector<int> ret;
        while ((int)ret.size() < num) {
            int x = randrange(l, r);
            if (!contain(ret, x)) {
                ret.push_back(x);
            }
        }
        sort(ret.begin(), ret.end());
        return ret;
    }
};

struct Timer {
    timespec start;
    Randomizer randomizer;

    Timer() {}

    Timer(int seed) {
        randomizer = Randomizer(seed);
    }

    void begin() {
        clock_gettime(CLOCK_REALTIME, &start);
    }

    double stopwatch() {
        timespec end;
        clock_gettime(CLOCK_REALTIME, &end);
        double sec = end.tv_sec - start.tv_sec;
        double nsec = end.tv_nsec - start.tv_nsec;
        return sec + nsec/1000000000;
    }

    bool scheduler(double delta, double time_limit, double t0, double t1) {
        assert(0.0 < time_limit && 0.0 <= t1 && t1 <= t0);
        if (0.0 <= delta) {
            return true;
        } else {
            double ratio = stopwatch() / time_limit;
            double t = pow(t0, 1.0-ratio) * pow(t1, ratio);
            return randomizer.uniform(0.0, 1.0) < pow(2.0, delta/t);
        }
    }
};

vector<int> tsp_solver(vector<vector<int>> cost_matrix) {
    // n を始点および終点とするTSPの厳密解を求める.
    int n = cost_matrix.size() - 1;
    int s = n;
    int inf = 1 << 30;
 
    // dp
    vector<vector<int>> dp(n, vector<int>(1<<n,inf));
    for (int i = 0; i < n; i++) {
        dp[i][1<<i] = cost_matrix[s][i];
    }
    for (int mask = 1; mask < 1<<n; mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask>>i & 1) == 0) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (mask>>j & 1) {
                    continue;
                }
                dp[j][mask^(1<<j)] = min(dp[j][mask^(1<<j)], dp[i][mask]+cost_matrix[i][j]);
            }
        }
    }
    // 経路復元
    int last = 0;
    int cost = inf;
    for (int i = 0; i < n; i++) {
        if (dp[i].back() + cost_matrix[i][s] < cost) {
            last = i;
            cost = dp[i].back() + cost_matrix[i][s];
        }
    }
    vector<int> ret = {last};
    int mask = (1<<n) - 1;
    mask ^= 1 << last;
    while (mask) {
        int j = ret.back();
        for (int i = 0; i < n; i++) {
            if (mask>>i & 1 && dp[i][mask] + cost_matrix[i][j] == dp[j][mask^1<<j]) {
                ret.push_back(i);
                mask ^= 1 << i;
                break;
            }
        }
        assert(ret.back() != j);
    }
    ret.push_back(s);
    reverse(ret.begin(), ret.end());
    return ret;
}

const int alpha = 5;
const double time_limit = 0.95;
const int inf = 1 << 30;

struct Solver {
    Timer timer;
    Randomizer randomizer;
    int n, m;
    vector<int> a, b;
    vector<vector<int>> groups;
    vector<int> c, d;

    Solver() {
        timer.begin();
    }

    void input() {
        cin >> n >> m;
        a = vector<int>(n);
        b = vector<int>(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i] >> b[i];
        }
    }

    pair<int,int> get_center(vector<int>& group) {
        if (group.empty()) {
            int j = randomizer.randrange(0, n);
            return {a[j], b[j]};
        }
        int x = 0;
        int y = 0;
        for (int i : group) {
            x += a[i];
            y += b[i];
        }
        return {x/(int)group.size(), y/(int)group.size()};
    }

    void k_means() {
        groups = vector<vector<int>>(m);
        for (int i = 0; i < m; i++) {
            groups[i].push_back(i);
        }
        for (int i = m; i < n; i++) {
            groups[randomizer.randrange(0,m)].push_back(i);
        }
        while (true) {
            vector<pair<int,int>> centers(m);
            for (int i = 0; i < m; i++) {
                centers[i] = get_center(groups[i]);
            }
            vector<vector<int>> new_groups(m);
            for (int i = 0; i < n; i++) {
                int best = 0;
                int min_cost = inf;
                for (int j = 0; j < m; j++) {
                    auto [x, y] = centers[j];
                    int cost = (a[i]-x)*(a[i]-x) + (b[i]-y)*(b[i]-y);
                    if (cost < min_cost) {
                        best = j;
                        min_cost = cost;
                    }
                }
                new_groups[best].push_back(i);
            }
            if (groups == new_groups) {
                break;
            }
            groups = new_groups;
        }
    }

    void solve() {
        k_means();
        c = vector<int>(m);
        d = vector<int>(m);
        for (int i = 0; i < m; i++) {
            pair<int,int> p = get_center(groups[i]);
            c[i] = p.first;
            d[i] = p.second;
        }
        vector<vector<int>> cost_matrix(m, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                int dist = (c[i]-c[j])*(c[i]-c[j]) + (d[i]-d[j])*(d[i]-d[j]);
                cost_matrix[i][j] = dist;
                cost_matrix[j][i] = dist;
            }
        }
        vector<int> order = tsp_solver(cost_matrix);
        int start = -1;
        for (int i = 0; i < m; i++) {
            if (contain(groups[order[i]], 0)) {
                start = i;
            }
        }
        vector<int> new_order(m);
        for (int i = 0; i < m; i++) {
            new_order[i] = order[(start+i) % m];
        }
        order = new_order;

        for (int i = 0; i < m; i++) {
            vector<pair<int,pair<int,int>>> data;
            for (int j : groups[i]) {
                data.push_back({j, {a[j]-c[i], b[j]-d[i]}});
            }
            sort(data.begin(), data.end(), [](const auto &a, const auto &b) {
                return atan2(a.second.second, a.second.first) < atan2(b.second.second, b.second.first);
            });
            int start = 0;
            if (contain(groups[i], 0)) {
                for (int j = 0; j < (int)data.size(); j++) {
                    if (data[j].first == 0) {
                        start = j;
                        break;
                    }
                }
            }
            for (int j = 0; j < (int)data.size(); j++) {
                groups[i][j] = data[(start+j) % (int)data.size()].first;
            }
        }

        for (int i = 0; i < m; i++) {
            cout << c[i] << ' ' << d[i] << '\n';
        }
        cout << 2*n + m + 1 << '\n';
        for (int i = 0; i < m; i++) {
            int station = order[i];
            for (int star : groups[station]) {
                cout << 1 << ' ' << star + 1 << '\n';
                cout << 2 << ' ' << station + 1 << '\n';
            }
            cout << 2 << ' ' << order[(i+1) % m] + 1 << '\n';
        }
        cout << 1 << ' ' << 1 << '\n';
    }
};

int main() {
    Solver solver;
    solver.input();
    solver.solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード