結果

問題 No.5007 Steiner Space Travel
ユーザー wanuiwanui
提出日時 2022-07-30 15:53:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 935 ms / 1,000 ms
コード長 7,896 bytes
コンパイル時間 3,123 ms
実行使用メモリ 3,664 KB
スコア 8,137,357
最終ジャッジ日時 2022-07-30 15:54:06
合計ジャッジ時間 32,921 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 906 ms
3,512 KB
testcase_01 AC 925 ms
3,524 KB
testcase_02 AC 908 ms
3,468 KB
testcase_03 AC 920 ms
3,512 KB
testcase_04 AC 910 ms
3,484 KB
testcase_05 AC 906 ms
3,576 KB
testcase_06 AC 907 ms
3,564 KB
testcase_07 AC 905 ms
3,604 KB
testcase_08 AC 928 ms
3,424 KB
testcase_09 AC 906 ms
3,572 KB
testcase_10 AC 921 ms
3,652 KB
testcase_11 AC 906 ms
3,488 KB
testcase_12 AC 905 ms
3,600 KB
testcase_13 AC 906 ms
3,608 KB
testcase_14 AC 906 ms
3,484 KB
testcase_15 AC 917 ms
3,580 KB
testcase_16 AC 906 ms
3,520 KB
testcase_17 AC 933 ms
3,552 KB
testcase_18 AC 906 ms
3,564 KB
testcase_19 AC 909 ms
3,492 KB
testcase_20 AC 907 ms
3,468 KB
testcase_21 AC 906 ms
3,516 KB
testcase_22 AC 931 ms
3,568 KB
testcase_23 AC 906 ms
3,488 KB
testcase_24 AC 931 ms
3,520 KB
testcase_25 AC 907 ms
3,664 KB
testcase_26 AC 905 ms
3,660 KB
testcase_27 AC 911 ms
3,516 KB
testcase_28 AC 907 ms
3,576 KB
testcase_29 AC 935 ms
3,556 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>;

double END_TIME = 900;
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;
}
pair<vector<pii>, vector<point>> kmeans() {
    // k-means

    // 初期値
    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 0);
    shuffle(perm.begin(), perm.end(), engine);
    vector<point> stations;
    for (int i = 0; i < M; i++) {
        stations.push_back(planets[perm[i]]);
    }

    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) {
                // cnt==0 はないと思うが... stationの位置に変更なし
                continue;
            }

            stations[sid] = {su.i / cnt, su.j / cnt};
        }
        pre_assign = assign;
    }
    vector<int> cluster_order(M);
    // クラスタをたどる順を全探索で探す(bitdpの方が速い)
    {
        int sid_init = pre_assign[0];
        vector<int> perm(M);
        iota(perm.begin(), perm.end(), 0);

        int mindist = 1e9;
        do {
            if (perm[0] != sid_init) continue;
            int s = 0;
            for (ll i = 0; i < M; i++) {
                s += distance2(stations[perm[i]], stations[perm[(i + 1) % M]]);
            }
            if (mindist > s) {
                mindist = s;
                cluster_order = perm;
            }
        } while (next_permutation(perm.begin(), perm.end()));
    }
    // station1->planet1.1->station1->planet1.2->station1->station2 のように移動
    // だが、planet1.1->planet1.2 のようにやるほうが短いならそれを選んでもよい
    vector<pii> ops;
    {
        ops.push_back({PLANET, 0});
        for (auto sid : cluster_order) {
            ops.push_back({STATION, sid});

            // 座圧？
            vector<int> i2p;
            map<int, int> p2i;
            for (int pid = 1; pid < N; pid++) {  // pid==0 は特別扱い
                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;
                    }
                }
            }
        }
        ops.push_back({STATION, cluster_order[0]});
        ops.push_back({PLANET, 0});
    }
    return {ops, stations};
}
void solve() {
    vector<pii> best_ops;
    vector<point> best_stations;
    int best_score = -1;
    while (now() < END_TIME) {
        vector<pii> ops;
        vector<point> stations;
        tie(ops, stations) = kmeans();
        int s = calc_score(ops, stations);
        if (s > best_score) {
            best_ops = ops;
            best_stations = stations;
            best_score = s;
        }
    }
    // 出力
    for (auto st : best_stations) {
        print(st.i, st.j);
    }
    print(best_ops.size());
    for (auto op : best_ops) {
        print(op.first, op.second + 1);
    }

    {
        perr("score=", best_score);
        perr("time=", int(now()));
    }
}
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