結果

問題 No.5007 Steiner Space Travel
ユーザー wanuiwanui
提出日時 2022-07-30 15:32:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 7,004 bytes
コンパイル時間 2,391 ms
実行使用メモリ 5,164 KB
スコア 7,873,133
最終ジャッジ日時 2022-07-30 15:32:25
合計ジャッジ時間 4,070 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on

// K-meansやりたい！
using pii = pair<int, int>;

mt19937 engine(0);
clock_t start_time;
double now() {
    return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
    start_time = clock();
    random_device seed_gen;
    engine.seed(seed_gen());
}

struct point {
    int i;
    int j;
};

const int PLANET = 1;
const int STATION = 2;
const int N = 100;
const int M = 8;
const int ALPHA = 5;

vector<point> planets(N);

int distance2(point a, point b) {
    return (a.i - b.i) * (a.i - b.i) + (a.j - b.j) * (a.j - b.j);
}
int calc_score(vector<pii> ops, vector<point> stations) {
    // round(10^9/(1000+sqrt(S)))
    double S = 0;
    int m = ops.size();
    for (int i = 1; i < m; i++) {
        pii pre = ops[i - 1];
        pii cur = ops[i];
        double ratio = 1;
        point pp;
        point cp;
        if (pre.first == STATION) {
            pp = stations[pre.second];
        } else {
            pp = planets[pre.second];
            ratio *= ALPHA;
        }
        if (cur.first == STATION) {
            cp = stations[cur.second];
        } else {
            cp = planets[cur.second];
            ratio *= ALPHA;
        }
        S += ratio * distance2(cp, pp);
    }
    return 1e9 / (1000.0 + sqrt(S)) + 0.5;
}
void solve() {
    // k-means
    // 初期値は固定(TODO)
    vector<point> stations = {
        {166, 166},
        {333, 500},
        {166, 833},
        {500, 666},
        {833, 833},
        {666, 500},
        {833, 166},
        {500, 333},
    };
    assert(stations.size() == M);

    vector<int> pre_assign(N, -1);
    for (int iter = 0; iter < 10000; iter++) {
        vector<int> assign(N);
        for (int pid = 0; pid < N; pid++) {
            auto pl = planets[pid];
            int mindist = 1e9;
            int minstation = -1;
            for (int sid = 0; sid < M; sid++) {
                auto st = stations[sid];
                int d = distance2(pl, st);
                if (mindist > d) {
                    mindist = d;
                    minstation = sid;
                }
            }
            assign[pid] = minstation;
        }
        if (pre_assign == assign) {
            break;
        }
        vector<point> sums(M, {0, 0});
        vector<int> counts(M);
        for (int pid = 0; pid < N; pid++) {
            auto pl = planets[pid];
            auto sid = assign[pid];
            sums[sid].i += pl.i;
            sums[sid].j += pl.j;
            counts[sid]++;
        }
        for (int sid = 0; sid < M; sid++) {
            int cnt = counts[sid];
            auto su = sums[sid];
            if (cnt == 0) {
                // TODO 初期値の選び方によってこれを起こさないことはできるが...
                // stationの位置に変更なし
                continue;
            }

            stations[sid] = {su.i / cnt, su.j / cnt};
        }
        pre_assign = assign;
    }
    // クラスタの移動は適当に決め打ち。 // TODO bitdpでできる
    // station1->planet1.1->station1->planet1.2->station1->station2 のように移動
    // だが、planet1.1->planet1.2 のようにやるほうが短いならそれを選んでもよい
    vector<pii> ops;
    {
        int sid = pre_assign[0];
        int sid_init = sid;
        ops.push_back({PLANET, 0});
        while (true) {
            // 座圧？
            vector<int> i2p;
            map<int, int> p2i;
            for (int pid = 0; pid < N; pid++) {
                if (pre_assign[pid] == sid) {
                    p2i[pid] = i2p.size();
                    i2p.push_back(pid);
                }
            }
            if (i2p.size() > 0) {
                // 距離に偏りのあるTSP. まずは貪欲 / TODO 焼きなましとかしたほうがよさそう
                int m = i2p.size();
                point st = stations[sid];
                vector<bool> done(m);
                int donenum = 0;
                while (true) {
                    pii cur = ops.back();
                    if (cur.first == STATION) {
                        // 適当に選ぶ
                        for (int i = 0; i < m; i++) {
                            if (!done[i]) {
                                ops.push_back({PLANET, i2p[i]});
                                break;
                            }
                        }
                        continue;
                    }
                    int pid = cur.second;
                    int i = p2i[pid];
                    done[i] = true;
                    donenum++;
                    if (donenum == m) {
                        ops.push_back({STATION, sid});
                        break;
                    }
                    int d_station = ALPHA * distance2(planets[pid], st);
                    int mind = d_station;
                    int minj = -1;
                    for (int j = 0; j < m; j++) {
                        if (done[j]) continue;
                        int dj = ALPHA * ALPHA * distance2(planets[pid], planets[i2p[j]]);
                        if (mind > dj) {
                            mind = dj;
                            minj = j;
                        }
                    }
                    if (minj == -1) {
                        ops.push_back({STATION, sid});
                        continue;
                    } else {
                        ops.push_back({PLANET, i2p[minj]});
                        continue;
                    }
                }
            }

            sid = (sid + 1) % M;
            if (sid == sid_init) break;
            ops.push_back({STATION, sid});
        }
        ops.push_back({STATION, sid_init});
        ops.push_back({PLANET, 0});
    }
    // 出力
    for (auto st : stations) {
        print(st.i, st.j);
    }
    print(ops.size());
    for (auto op : ops) {
        print(op.first, op.second + 1);
    }

    {
        perr("time=", now());
        perr("score=", calc_score(ops, stations));
    }
}
int main() {
    marathon_init();
    ioinit();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        planets[i] = {i : a, j : b};
    }
    solve();
    return 0;
}
0