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

• 問題: No.5007 Steiner Space Travel
• ユーザー: highjump
• 提出日時: 2023-04-25 22:49:35
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 953 ms / 1,000 ms
• コード長: 10,339 bytes
• コンパイル時間: 2,759 ms
• コンパイル使用メモリ: 162,000 KB
• 実行使用メモリ: 8,432 KB
• スコア: 8,029,875
• 最終ジャッジ日時: 2023-04-25 22:50:10
• 合計ジャッジ時間: 34,259 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	953 ms; 8,268 KB
testcase_01	AC	952 ms; 8,136 KB
testcase_02	AC	952 ms; 8,332 KB
testcase_03	AC	952 ms; 8,116 KB
testcase_04	AC	953 ms; 8,432 KB
testcase_05	AC	953 ms; 8,220 KB
testcase_06	AC	953 ms; 8,144 KB
testcase_07	AC	953 ms; 8,200 KB
testcase_08	AC	952 ms; 8,336 KB
testcase_09	AC	952 ms; 8,196 KB
testcase_10	AC	952 ms; 8,196 KB
testcase_11	AC	953 ms; 8,132 KB
testcase_12	AC	953 ms; 8,204 KB
testcase_13	AC	952 ms; 8,244 KB
testcase_14	AC	953 ms; 8,176 KB
testcase_15	AC	952 ms; 8,144 KB
testcase_16	AC	953 ms; 8,228 KB
testcase_17	AC	952 ms; 8,284 KB
testcase_18	AC	953 ms; 8,372 KB
testcase_19	AC	951 ms; 8,252 KB
testcase_20	AC	952 ms; 8,256 KB
testcase_21	AC	952 ms; 8,144 KB
testcase_22	AC	953 ms; 8,124 KB
testcase_23	AC	952 ms; 8,332 KB
testcase_24	AC	953 ms; 8,216 KB
testcase_25	AC	952 ms; 8,116 KB
testcase_26	AC	952 ms; 8,264 KB
testcase_27	AC	952 ms; 8,228 KB
testcase_28	AC	953 ms; 8,256 KB
testcase_29	AC	952 ms; 8,136 KB

ソースコード

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>  
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

using ll = long long;
using P = pair<int, int>;
template <class T>using V = vector<T>;
template <class T>using VV = V<V<T>>;
template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }
template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }

#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)
#define MP make_pair
#define SZ(x) int(x.size())
#define ALL(x) x.begin(),x.end()
#define INF 10001000
#define endl "\n"

chrono::system_clock::time_point t_start;
const double TIME_LIMIT1 = 500, TIME_LIMIT = 950;
double last_update = 0, t_diff;
double start_temp, end_temp;

mt19937 rng;
using uni_int = uniform_int_distribution<>;
using uni_real = uniform_real_distribution<>;
using u64 = uint64_t;
using u32 = uint32_t;

V<int> y_vec = { 0, 1,0, -1 };
V<int> x_vec = { -1, 0,1, 0 };

class XorInt {
public:
    uint32_t x = 2463534242;

    XorInt() {};

    XorInt(uint32_t seed) {
        x = 2463534242 + seed;
    };

    uint32_t next() {
        x ^= x << 13; x ^= x >> 17; x ^= x << 5;
        return x;
    }

    uint32_t operator()(uint32_t l, uint32_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint32_t operator()(uint32_t d) {
        return this->next() % d;
    }
};

XorInt xs;

class Xor64 {
public:
    uint64_t x = 88172645463325252ULL;

    Xor64() {};

    Xor64(uint64_t seed) {
        x = 88172645463325252ULL + seed;
    }

    uint64_t next() {
        x ^= x << 13; x ^= x >> 7; x ^= x << 17;
        return x;
    }

    uint64_t operator()(uint64_t l, uint64_t r) {
        return (this->next() % (r - l)) + l;
    }

    uint64_t operator()(uint64_t d) {
        return this->next() % d;
    }
};

Xor64 xx;

void get_time() {
    auto t_now = chrono::system_clock::now();
    t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}

int N, M;
const int A = 5;
int score = 0;
int bestScore = 0;
int cnt = 0;

VV<int> candidates;
VV<int> distances;
VV<int> destinations;

class Pos {
public:
    int x = 0;
    int y = 0;
    int kind = 0;
    int order = 0;

    Pos() {};
    Pos(int sx, int sy) :x(sx), y(sy) {};
    Pos(int sx, int sy, int o) :x(sx), y(sy), order(o) {};


};

class Planet :public Pos {
public:

    Planet() { kind = 1; };
    Planet(int sx, int sy, int o) :Pos(sx, sy, o) { kind = 1; };

};

class Station :public Pos {
public:

    Station() { kind = 2; };
    Station(int sx, int sy, int o) :Pos(sx, sy, o) { kind = 2; };

};

int Diff(int lx, int ly, int rx, int ry) {
    return (lx - rx) * (lx - rx) + (ly - ry) * (ly - ry);
}

int getFuel(Pos& l, Pos& r) {
    int dis = (l.x - r.x) * (l.x - r.x) + (l.y - r.y) * (l.y - r.y);
    if (l.kind != r.kind)
        return dis * A;
    if (l.kind == 1)
        return dis * A * A;
    return dis;
}

V<Planet> planets;
V<Station> stations;

Pos& setPos(int k) {
    if (k < N)return planets[k];
    return stations[k % N];
}

int getScore(V<int>& route) {
    int sumFuel = 0;
    FOR(i, 1, route.size() - 1) {
        Pos& current = setPos(route[i - 1]);
        Pos& target = setPos(route[i]);
        sumFuel += getFuel(current, target);
    }

    return int(round(1000000000.0 / (1000.0 + sqrt(sumFuel))));
}

V<int> exchange(bitset<700>& route,int init) {
    V<int> res;
    REP(i, N) {
        int id = 0;
        int base = 1;
        REP(bit, 7) {
            if (route[i * 7 + bit] == 1) {
                id += base;
            }
            base <<= 1;
        }
        res.push_back(id);
    }
    res.push_back(init);
    return res;
}

class State {
public:
    int fuel = 0;
    int counter = 0;
    int last = 0;
    int init = 0;
    bitset<100> visited;
    bitset<700> route;

    State() {};
    State(int init):init(init) {};

    void addPlanet(int id) {
        REP(i, 7) {
            if ((id >> i) & 1) {
                route.set(counter * 7 + i);
            }
        }
    }

    void play(int target) {
        if (target < N) {
            visit(target);
            counter++;
        }
        
        fuel += distances[last][target];
        last = target;
    }

    void visit(int id) {
        visited.set(id);
    }

    bool isVisited(int id) {
        return visited[id] == 1;
    }
};

bool operator < (const State& l, const State& r) {
    return l.fuel > r.fuel;
}

void calcCenter(V<int>& labels, V<P>& centers) {
    V<int> counter(M);
    REP(i, M)centers[i] = MP(0, 0);
    REP(i, N) {
        Planet& planet = planets[i];
        counter[labels[i]]++;
        centers[labels[i]].first += planet.x;
        centers[labels[i]].second += planet.y;
    }
    REP(i, M) {
        if (counter[i] == 0) {
            continue;
        }
        centers[i].first /= counter[i];
        centers[i].second /= counter[i];
    }
}

int reallocate(V<int>& labels, V<P>& centers) {
    int res = 0;
    REP(i, N) {
        Planet& planet = planets[i];
        int newLabel = labels[i];
        int minDiff = INF;
        REP(label, M) {
            if (chmin(minDiff, Diff(planet.x, planet.y, centers[label].first, centers[label].second)))
                newLabel = label;
        }
        if (newLabel != labels[i])res++;
        labels[i] = newLabel;
    }
    return res;
}

void kmeans(V<int>& xpos, V<int>& ypos) {
    V<int> labels(N);
    REP(i, N)labels[i] = i%M;
    V<P> centers(M);
    calcCenter(labels, centers);
    REP(i, 300) {
        int diff=reallocate(labels, centers);
        if (diff == 0)break;
        calcCenter(labels, centers);
    }
    REP(i, M) {
        if (centers[i].first == 0)continue;
        xpos[i] = centers[i].first;
        ypos[i] = centers[i].second;
    }
}

void wfroid() {
    REP(i, N + M)REP(j, N + M) {
        destinations[i][j] = j;
        if (i == j) {
            distances[i][j] = 0;
            continue;
        }
        distances[i][j] = getFuel(setPos(i), setPos(j));
    }

    REP(k, N + M) {
        REP(i, N + M) {
            REP(j, N + M) {
                if(chmin(distances[i][j], distances[i][k] + distances[k][j]))
                    destinations[i][j]=destinations[i][k];
            }
        }
    }
}

void setup() {
    candidates = VV<int>(N);
    planets = V<Planet>(N);
    stations = V<Station>(M);
    distances = VV<int>(N + M, V<int>(N + M,INF));
    destinations = VV<int>(N + M, V<int>(N + M));


    REP(i, N) {
        int x, y; cin >> x >> y;
        planets[i] = Planet(x, y, i + 1);
    }

    V<int> xpos = { 250,500,750,250,750,250,500,750 };
    V<int> ypos = { 250,250,250,500,500,750,750,750 };

    kmeans(xpos, ypos);

    REP(i, M) {
        int x = xpos[i];
        int y = ypos[i];
        stations[i] = Station(x, y, i + 1);
    }

    REP(i, N) {
        FOR(j, 0, N-1) {
            if (i == j)continue;
            candidates[i].push_back(j);
        }
    }

    wfroid();
}

V<int> chokudaiSearch(int beam_width) {
    int beam_depth = N;
    auto beam = V<priority_queue<State>>(beam_depth + 1);
    REP(t, beam_depth + 1) {
        beam[t] = priority_queue<State>();
    }
    State initState(0);
    initState.addPlanet(0);
    beam[0].push(initState);
    while (t_diff < TIME_LIMIT) {
        REP(t, beam_depth) {
            auto& now_beam = beam[t];
            auto& next_beam = beam[t + 1];
            int max_load = 300;
            if (SZ(now_beam) > max_load) {
                priority_queue<State> pool;
                REP(i, max_load / 2) {
                    pool.push(now_beam.top());
                    now_beam.pop();
                }
                now_beam.swap(pool);
            }
            REP(i, beam_width) {
                if (now_beam.empty())break;
                State now_state = now_beam.top();
                now_beam.pop();
                if (t == N - 1) {
                    State newState = now_state;
                    newState.play(newState.init);
                    next_beam.push(newState);
                }
                else {
                    for(auto npos:candidates[now_state.last]) {
                        if (now_state.isVisited(npos)||npos==now_state.init)continue;
                        State newState = now_state;
                        newState.play(npos);
                        newState.addPlanet(npos);
                        next_beam.push(newState);

                    }
                }
            }
            get_time();
            if (t_diff > TIME_LIMIT&&!beam[N].empty())break;
        }
        cnt++;
        if (t_diff > TIME_LIMIT && !beam[N].empty())break;
    }
    bitset<700> bestRoute = beam[N].top().route;
    return exchange(bestRoute, beam[N].top().init);
}

void out(V<int>& route) {
    REP(i, M) {
        cout << stations[i].x << " " << stations[i].y << endl;
    }
    cout << route.size() << endl;
    for (auto p : route) {
        Pos& pos = setPos(p);
        cout << pos.kind << " " << pos.order << endl;
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    t_start = chrono::system_clock::now();

    get_time();
    cin >> N >> M;

    setup();
    V<int> route;
    route = chokudaiSearch(1);

    V<int>new_route;
    new_route.push_back(0);

    FOR(i, 1, N) {
        int temp = route[i - 1];
        int next = route[i];
        int mid = destinations[temp][next];
        while (true) {
            new_route.push_back(mid);
            if (mid == next)break;
            mid = destinations[mid][next];
        }
    }

    score = getScore(new_route);
    out(new_route);
    get_time();

    cerr << "time=" << int(t_diff) << " ms" << endl;
    cerr << "score=" << score << endl;
    //cerr << "last=" << last_update << endl;
    cerr << "cnt=" << cnt << endl;
    //cerr << "update=" << update_cnt << endl;
    return 0;
}