結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー tmikada
提出日時 2023-04-29 13:45:22
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,787 bytes
コンパイル時間 2,405 ms
コンパイル使用メモリ 208,140 KB
実行使用メモリ 4,376 KB
スコア 4,521,707
最終ジャッジ日時 2023-04-29 13:45:27
合計ジャッジ時間 4,623 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

using namespace std;
using ll=long long;

// Start 2023.04.23 21:00 
// End   
// Time  min

// MTK005

constexpr ll TYPE_PLANET = 1;
constexpr ll TYPE_STATION = 2;
constexpr ll ALPHA = 5;

struct Pos {
    int x,y;
    ll type;
    Pos(int x, int y, ll type) : x(x), y(y), type(type) {}
};
std::ostream& operator<<(std::ostream& os, const Pos& pos) {
    std::ostringstream oss;
    oss << "(" << pos.x << ", " << pos.y << "), " << pos.type << "";
    os << oss.str();
    return os;
}

struct Solver {
	int N = 0;
	int M = 0;
    vector<Pos> points;

    Solver(int n, int m, vector<Pos>& points) : N(n),M(m),points(points) {}

    void test() {
        debug(N,M,points);
    }

    void solve() {
        // 貪欲法
        // 宇宙ステーションの座標は適当に決め打ち
        set_station();
        debug(points);

        // 惑星1からスタートする
        // 一番近い惑星＋宇宙ステーションを選び続ける
        vector<int> visited(N+M,0);
        vector<int> route;
        visited[0]++;
        route.push_back(0);

        int v = 0;
        for(int i=0; i<N; i++) {
            int nearest_dist = INT_MAX;
            int nearest_v = -1;

            // 一番近い惑星を探す
            for(int next=0; next<N; next++) {
                if(next < N && visited[next] > 0) continue;

                int d = calc_energy(v,next);
                if(d < nearest_dist) {
                    nearest_dist = d;
                    nearest_v = next;
                }
                debug(d);
            }
            // 次の頂点に移動
            if(nearest_v != -1) {
                v = nearest_v;
                visited[v]++;
                route.push_back(nearest_v);
            }
        }
        // 最後に惑星1に戻る
        route.push_back(0);
        debug(visited);

        debug(route);  
        output(route);      
    }

    void output(vector<int>& route) {
        // 宇宙ステーションの座標
        for(int i=N; i<N+M; i++) {
            if(points[i].type == TYPE_STATION) {
                cout << points[i].x << " " << points[i].y << endl;
            }
        }

        // 経路の長さ
        cout << route.size() << endl;

        // 経路
        for(auto i : route) {
            Pos pos = points[i];
            if(pos.type == TYPE_PLANET) {
                cout << pos.type << " " << i+1 << endl;
            }
            else {
                cout << pos.type << " " << i+1-N << endl;
            }
        }
    }

    void set_station() {
        for(int i=0; i<M; i++) {
            points.emplace_back(Pos(RandInt(0,1000),RandInt(0,1000),TYPE_STATION));
        }
    }

    // a以上b以下のランダム
    int RandInt(int a, int b) {
        return a + rand() % (b-a+1);
    }

    int calc_energy(int i, int j) {
        int dx, dy;
        int energy;
        auto [x1, y1, type1] = points[i];
        auto [x2, y2, type2] = points[j];
        dx = x1 - x2;
        dy = y1 - y2;
        energy = dx * dx + dy * dy;

        // 惑星かどうか判定
        if (type1 == TYPE_PLANET)
        {
            energy *= 5;
        }
        if (type2 == TYPE_PLANET)
        {
            energy *= 5;
        }
        return energy;
    }

};

int main() {

    int n,m;
    cin >> n >> m;
    // vector<int> a(n),b(n);
    vector<Pos> points;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a >> b;
        points.emplace_back(Pos(a,b,TYPE_PLANET));
    }
    debug(n,m,points);

    Solver solver(n,m,points);
    solver.solve();

	return 0;
}
0