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

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	tabae326
提出日時	2023-04-24 21:44:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	805 ms / 1,000 ms
コード長	15,210 bytes
コンパイル時間	5,831 ms
コンパイル使用メモリ	286,948 KB
実行使用メモリ	4,372 KB
スコア	7,799,831
最終ジャッジ日時	2023-04-24 21:44:58
合計ジャッジ時間	32,462 ms
ジャッジサーバーID （参考情報）	judge13 / judge14
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#include <bits/stdc++.h>
#include <sys/time.h>
#include <atcoder/all>

using namespace std;

#pragma region prototype_declaration
/* ============================================== 
    プロトタイプ宣言はここから
   ============================================== */

/*乱数生成器*/
struct RandGenerator {
    random_device seed_gen;
    mt19937 engine;
    mt19937_64 engine64;
    static const int pshift = 1000000000;
    RandGenerator() : engine(seed_gen()), engine64(seed_gen()) {}
    /*mod以下の乱数を返す（32bit）*/
    int rand(int mod) {
        return engine() % mod;
    }
    /*mod以下の乱数を返す（64bit）*/
    long long randll(long long mod) {
        return engine64() % mod;
    } 
    /*確率pでTrueを返す*/
    bool pjudge(double p) {
        int p_int;
        if(p > 1) p_int = pshift;
        else p_int = p * pshift;
        return rand(pshift) < p_int;
    }
} ryuka;

/*タイマー*/
struct Timer {
    double global_start;
    /*現在の時刻を返す*/
    double gettime() {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }
    void init() {
        global_start = gettime();
    }
    /*プログラム開始からの経過時間を返す*/
    double elapsed() {
        return gettime() - global_start;
    }
} toki;

struct Node {
    enum Type {
        planet,
        station
    };
    int x, y, id, to, from;
    Type type;
    Node() : to(-1), from(-1) {};
    Node(int, int, int, Type);
};

struct Input {
    /*TODO: ここに入力変数を定義する*/
    int n, m;
    const int a = 5;
    vector<Node> planets;
    void read();
} input;

struct Output {
    /*TODO: ここに出力変数を定義する*/
    vector<Node> stations;
    vector<Node> route; 
    Output();
    void print();
};

/*解を管理するクラス*/
struct State {
    Output output;
    long long length;
    long long score;
    State() : score(0) {}
    static State initState();
    static State generateState(const State& input_state);
};

/*イテレーション管理クラス*/
template<class STATE>
struct IterationControl {
    int iteration_counter;
    int swap_counter;
    double average_time;
    double start_time;
    IterationControl() : iteration_counter(0), swap_counter(0) {}
    /*山登り法*/
    STATE climb(double time_limit, STATE initial_state) {
        start_time = toki.gettime();
        average_time = 0;
        STATE best_state = initial_state;
        double time_stamp = start_time;
        cerr << "[INFO] - IterationControl::climb - Starts climbing...\n";
        while(time_stamp - start_time + average_time < time_limit) {
            STATE current_state = STATE::generateState(best_state);
            if(current_state.score > best_state.score) {
                swap(best_state, current_state);
                swap_counter++;
            }
            iteration_counter++;
            time_stamp = toki.gettime();
            average_time = (time_stamp - start_time) / iteration_counter;
        }
        cerr << "[INFO] - IterationControl::climb - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
        return best_state;
    }
    /*焼きなまし法*/
    STATE anneal(double time_limit, double temp_start, double temp_end, STATE initial_state) {
        assert(temp_start >= temp_end);
        start_time = toki.gettime();
        average_time = 0;
        STATE best_state = initial_state;
        double elapsed_time = 0;
        cerr << "[INFO] - IterationControl::anneal - Starts annealing...\n";
        while(elapsed_time + average_time < time_limit) {
            double normalized_time = elapsed_time / time_limit;
            double temp_current = pow(temp_start, 1.0 - normalized_time) * pow(temp_end, normalized_time);
            STATE current_state = STATE::generateState(best_state);
            long long delta = current_state.score - best_state.score;
            if(delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current)) ) {
                swap(best_state, current_state);
                swap_counter++;
            }
            iteration_counter++;
            elapsed_time = toki.gettime() - start_time;
            average_time = elapsed_time / iteration_counter;
        }
        cerr << "[INFO] - IterationControl::anneal - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
        return best_state;
    }
};

namespace Utils {
    int calcSquareDist(const Node& a, const Node& b);
    bool isPlanet(const Node& node);
    bool isStart(const Node& node);
    pair<long long, long long> calcScore(const Output& output);
    long long calcScoreFromLength(long long length);
    vector<Node> initStations();
    vector<Node> solveInsertedTSP(const vector<Node>& stations);
    vector<Node> insertStations(const vector<Node>& nodes);
    pair<vector<Node>, vector<Node>> goThroughStations(const vector<Node>& nodes);
    vector<Node> rearrangeRoute(const vector<Node>& nodes);
};

/* ============================================== 
    プロトタイプ宣言はここまで
   ============================================== */

#pragma endregion prototype_declaration

Node::Node(int x, int y, int id, Node::Type type) : 
    x(x), y(y), id(id), type(type) {
        ;
}

/*TODO: ここで入力を受け取る*/
void Input::read() {
    cin >> n >> m;
    planets.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> planets[i].x >> planets[i].y;
        planets[i].id = i;
        planets[i].type = Node::Type::planet;
    }
}

/*TODO：ここで出力変数を初期化する。vectorのメモリ確保など*/
Output::Output() {
}

/*TODO：ここで答えを出力する*/
void Output::print() {
    assert(stations.size() == input.m);
    for(auto e : stations) {
        cout << e.x << " " << e.y << endl;
    }
    cout << route.size() << endl;
    for(auto e : route) {
        cout << (Utils::isPlanet(e) ? 1 : 2) << " " << e.id + 1 << endl;
    }
}

/*TODO: ここで初期解を作成する*/
State State::initState() {
    State res;
    res.output.route = Utils::solveInsertedTSP(vector<Node>());
    auto [score, length] = Utils::calcScore(res.output);
    res.score = score;
    res.length = length;
    return res;
}

/*TODO: ここでinput_stateを変化させた解を作る（局所探索）*/
State State::generateState(const State& input_state) {
    State res = input_state;
    int i = ryuka.rand(res.output.route.size());
    int j = ryuka.rand(res.output.route.size());
    int i2 = res.output.route[i].to;
    int j2 = res.output.route[j].to;
    bool chk = (i != j) && (i != j2) && (j != i2); 
    if(chk) {
        res.length -= input.a * input.a * Utils::calcSquareDist(res.output.route[i], res.output.route[i2]);
        res.length -= input.a * input.a * Utils::calcSquareDist(res.output.route[j], res.output.route[j2]);
        res.length += input.a * input.a * Utils::calcSquareDist(res.output.route[i], res.output.route[j]);
        res.length += input.a * input.a * Utils::calcSquareDist(res.output.route[j2], res.output.route[i2]);
        res.output.route[i].to = j;
        res.output.route[j2].from = i2;
        int cur = j;
        while(true) {
            int nxt = res.output.route[cur].from;
            swap(res.output.route[cur].from, res.output.route[cur].to);
            if(cur == j) res.output.route[cur].from = i;
            if(cur == i2) {
                res.output.route[cur].to = j2;
                break;
            }
            cur = nxt;
        }
        res.score = Utils::calcScoreFromLength(res.length);
    }
    return res;
}

int Utils::calcSquareDist(const Node& a, const Node& b) {
    const int dx = a.x - b.x;
    const int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

bool Utils::isStart(const Node& node) {
    return isPlanet(node) && node.id == 0;
}

bool Utils::isPlanet(const Node& node) {
    return node.type == Node::Type::planet;
}

/*TODO: ここでスコアを計算する*/
pair<long long, long long> Utils::calcScore(const Output& output) {
    long long sum = 0;
    const auto& route = output.route;
    int debug = 0;
    Node cur = route.front();
    assert(Utils::isStart(cur));
    while(true) {
        Node nxt = route[cur.to];
        const long long d2 = Utils::calcSquareDist(cur, nxt);
        if(isPlanet(cur) && isPlanet(nxt)) {
            sum += input.a * input.a * d2; 
        } else if(!isPlanet(cur) && !isPlanet(nxt)) {
            sum += d2;
        } else {
            debug++;
            sum += input.a * d2;
        }
        cur = nxt;
        if(Utils::isStart(cur)) break;
    }
    long long res = (long long)(1e9 / (1e3 + sqrt(sum)));
    return {res, sum};
}

long long Utils::calcScoreFromLength(long long length) {
    long long res = (long long)(1e9 / (1e3 + sqrt(length)));
    return res;
}

vector<Node> Utils::rearrangeRoute(const vector<Node>& route) {
    vector<Node> res;
    Node cur = route.front();
    while(true) {
        Node nxt = route[cur.to];
        res.push_back(cur);
        if(Utils::isStart(nxt)) {
            res.push_back(nxt);
            break;
        }
        cur = nxt;
    }
    return res;
}

vector<Node> Utils::solveInsertedTSP(const vector<Node>& stations) {
    vector<Node> nodes, route;
    for(auto e: input.planets) if(e.id != 0) nodes.push_back(e);
    for(auto e: stations) nodes.push_back(e);
    route.push_back(input.planets.front());
    route.push_back(input.planets.front());
    shuffle(route.begin(), route.end(), ryuka.engine);
    for(auto e: nodes) {
        int min_dist = 1<<30, min_id = -1;
        for(int i = 0; i < route.size() - 1; i++) {
            int dist = Utils::calcSquareDist(e, route[i]) + Utils::calcSquareDist(e, route[i+1]);
            if(min_dist > dist) {
                min_dist = dist;
                min_id = i + 1;
            }
        }
        assert(min_id != -1);
        route.insert(route.begin() + min_id, e);
    }
    for(int i = 0; i < route.size() - 2; i++) route[i].to = i+1;
    for(int i = 1; i < route.size() - 1; i++) route[i].from = i-1;
    route[route.size()-2].to = 0;
    route[0].from = route.size() - 2;
    route.pop_back();
    return route;
}

vector<Node> Utils::insertStations(const vector<Node>& nodes) {
    vector<pair<int, int>> v;
    vector<Node> res = nodes;
    for(int i = 0; i < res.size(); i++) {
        v.push_back({Utils::calcSquareDist(res[i], res[res[i].to]), i});
    } 
    sort(v.begin(), v.end(), greater<pair<int,int>>());
    sort(v.begin(), v.begin() + min<int>(input.m, v.size()), [](auto l, auto r) {
        return l.second < r.second;
    });
    vector<pair<int, Node>> inserted;
    for(auto [_, i]: v) {
        int nx = min(res[i].x, res[res[i].to].x) + abs(res[i].x - res[res[i].to].x) / 2; 
        int ny = min(res[i].y, res[res[i].to].y) + abs(res[i].y - res[res[i].to].y) / 2; 
        inserted.push_back({i, Node(nx, ny, inserted.size(), Node::Type::station)});
        if(inserted.size() == input.m) break;
    }
    for(auto [i, node]: inserted) {
        int ri = res.size();
        node.to = res[i].to;
        res[i].to = ri;
        res.push_back(node);
    }
    return res;
}

vector<Node> Utils::initStations() {
    vector<int> cluster(input.n, 0);
    for(int i = 0; i < input.n; i++) {
        cluster[i] = i % input.m;
    }
    vector<int> prev;
    int count = 0;
    const int iter_max = 1000;
    while(prev != cluster && count < iter_max) {
        vector<long long> w_x(input.m, 0);
        vector<long long> w_y(input.m, 0);
        vector<int> num(input.m, 0);
        for(int i = 0; i < input.n; i++) {
            w_x[cluster[i]] += input.planets[i].x;
            w_y[cluster[i]] += input.planets[i].y;
            num[cluster[i]]++;
        }
        for(int i = 0; i < input.m; i++) {
            if(num[i] > 0) {
                w_x[i] /= num[i];
                w_y[i] /= num[i];
            }
        }
        for(int i = 0; i < input.n; i++) {
            int min_dist = 1<<30, min_id = -1;
            for(int j = 0; j < input.m; j++) {
                int dist = Utils::calcSquareDist(input.planets[i], Node(w_x[j], w_y[j], -1, Node::Type::station));
                if(dist < min_dist) {
                    min_dist = dist;
                    min_id = j;
                }
            }
            assert(min_id != -1);
            cluster[i] = min_id;
        }
        count++;
    }
    if(count >= iter_max) {
        cerr << "[WARNING] - Utils::initStations - Failed to k-means" << endl;
        /*
        for(int i = 0; i < input.n; i++) {
            cerr << cluster[i] << " " << input.planets[i].x << " " << input.planets[i].y << endl;
        }
        */
    }
    vector<Node> res(input.m);
    vector<long long> w_x(input.m, 0);
    vector<long long> w_y(input.m, 0);
    vector<int> num(input.m, 0);
    for(int i = 0; i < input.n; i++) {
        w_x[cluster[i]] += input.planets[i].x;
        w_y[cluster[i]] += input.planets[i].y;
        num[cluster[i]]++;
    }
    for(int i = 0; i < input.m; i++) {
        if(num[i] > 0) {
            w_x[i] /= num[i];
            w_y[i] /= num[i];
        }
    }
    for(int i = 0; i < input.m; i++) {
        res[i] = Node(w_x[i], w_y[i], i, Node::Type::station);
    }   
    return res;
}

pair<vector<Node>, vector<Node>> Utils::goThroughStations(const vector<Node>& route) {
    vector<Node> res;
    vector<Node> stations = Utils::initStations();
    Node cur = route.front();
    int prev = -1;
    while(true) {
        Node nxt = route[cur.to];
        int cur_pos = res.size();
        cur.from = prev;
        cur.to = cur_pos + 1;
        prev = cur_pos;
        res.push_back(cur);
        int min_dist = input.a * Utils::calcSquareDist(cur, nxt);
        Node min_node;
        bool insert = false;
        for(auto st: stations) {
            int dist = Utils::calcSquareDist(cur, st) + Utils::calcSquareDist(st, nxt);
            if(dist < min_dist) {
                min_dist = dist;
                min_node = st;
                insert = true;
            }
        }
        if(insert) {
            cur.to = min_node.id;
            int cur_pos = res.size();
            prev = cur_pos;
            min_node.from = cur_pos - 1;
            min_node.to = cur_pos + 1;
            res.push_back(min_node);
        }
        if(Utils::isStart(nxt)) {
            res[0].from = res.size() - 1;
            res[res.size()-1].to = 0;
            break;
        }
        cur = nxt;
    }
    return {res, stations};
}

int main(int argc, char* argv[]) {
    toki.init();
    input.read();   
    IterationControl<State> sera;
    State ans = sera.anneal(0.8, 1e5, 50, State::initState());
    //State ans = sera.climb(0.8, State::initState());
    //State ans = State::initState();
    auto [route, stations] = Utils::goThroughStations(ans.output.route);
    ans.output.route = route;
    ans.output.stations = stations;
    ans.score = Utils::calcScore(ans.output).first;
    ans.output.route = Utils::rearrangeRoute(ans.output.route);
    ans.output.print();
    cerr << "[INFO] - main - MyScore = " << ans.score << "\n";
}
yukicoder

結果

テストケース

ソースコード
