結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 BinomialSheep
|
| 提出日時 | 2022-08-02 01:56:35 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 20 ms / 1,000 ms |
| コード長 | 10,755 bytes |
| コンパイル時間 | 4,969 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 6,203,930 |
| 最終ジャッジ日時 | 2022-08-02 01:56:42 |
| 合計ジャッジ時間 | 4,672 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
// デバッグ用マクロ：https://naskya.net/post/0002/
#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 namespace chrono;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvi = vector<vector<vector<int>>>;
using pii = pair<int, int>;
// #include <atcoder/all>
// using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
// #define MAX 10000
#define INFTY (1 << 30)
// 浮動小数点の誤差を考慮した等式
#define EPS (1e-10)
#define equal(a, b) (fabs((a) - (b)) < EPS)
template <typename T>
inline bool chmax(T &a, T b) {
return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
return ((a > b) ? (a = b, true) : (false));
}
// 焼きなまし法の参考にしたページ
// https://shindannin.hatenadiary.com/entry/2021/03/06/115415
// 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift
// https://ja.wikipedia.org/wiki/Xorshift
static uint32_t randXor() {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
// 0以上1未満の小数をとる乱数
static double rand01() { return (randXor() + 0.5) * (1.0 / UINT_MAX); }
struct Solver {
int N, M;
vi a, b;
// α
int A = 5;
vpii stupidInit() {
vpii ret;
rep(i, N) ret.emplace_back(1, i + 1);
ret.emplace_back(1, 1);
return ret;
}
// 惑星を経由しない
vpii greedyInit() {
vpii ret;
vector<vpii> distList(N);
auto dist = [](int x1, int y1, int x2, int y2) {
return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
rep(i, N) rep(j, i) {
int x1 = a[i];
int y1 = b[i];
int x2 = a[j];
int y2 = b[j];
auto d = A * A * dist(x1, y1, x2, y2);
distList[i].emplace_back(d, j);
distList[j].emplace_back(d, i);
}
rep(i, N) sort(all(distList[i]));
vi color(N);
int now = 0;
color[0] = 1;
ret.emplace_back(1, 1);
rep(i, N) {
for (auto p : distList[now]) {
if (color[p.second]) continue;
now = p.second;
color[p.second] = 1;
ret.emplace_back(1, now + 1);
break;
}
}
ret.emplace_back(1, 1);
return ret;
}
// 惑星を経由する
vpii greedyInit2(vpii &cd) {
vpii ret;
vector<vpii> distList(N);
map<pii, vpii> mp;
auto dist = [&](int x1, int y1, int x2, int y2, int xi, int yi) {
vpii value;
ll dt = A * A * (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
rep(i, (int)cd.size()) {
auto x = cd[i].first;
auto y = cd[i].second;
ll tmp = A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y));
tmp += A * (ll)((x - x2) * (x - x2) + (y - y2) * (y - y2));
if (chmin(dt, tmp)) {
value.clear();
value.emplace_back(2, i + 1);
}
}
ll tmp1 = INFTY;
ll tmp2 = INFTY;
int idx1, idx2;
rep(i, (int)cd.size()) {
auto x = cd[i].first;
auto y = cd[i].second;
if (chmin(tmp1, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))))
idx1 = i;
if (chmin(tmp2, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))))
idx2 = i;
}
if (idx1 != idx2) {
auto xx1 = cd[idx1].first;
auto yy1 = cd[idx1].first;
auto xx2 = cd[idx2].first;
auto yy2 = cd[idx2].first;
ll tmp3 = (ll)((xx1 - xx2) * (xx1 - xx2) + (yy1 - yy2) * (yy1 - yy2));
if (chmin(dt, tmp1 + tmp2 + tmp3)) {
value.clear();
value.emplace_back(2, idx1 + 1);
value.emplace_back(2, idx2 + 1);
}
}
mp[make_pair(xi, yi)] = value;
return dt;
};
rep(i, N) rep(j, i) {
int x1 = a[i];
int y1 = b[i];
int x2 = a[j];
int y2 = b[j];
auto d = A * A * dist(x1, y1, x2, y2, i, j);
mp[make_pair(j, i)] = mp[make_pair(i, j)];
distList[i].emplace_back(d, j);
distList[j].emplace_back(d, i);
}
rep(i, N) sort(all(distList[i]));
vi color(N);
int now = 0;
color[0] = 1;
ret.emplace_back(1, 1);
rep(i, N) {
for (auto p : distList[now]) {
if (color[p.second]) continue;
for (auto pp : mp[make_pair(now, p.second)]) {
ret.push_back(pp);
}
ret.emplace_back(1, p.second + 1);
now = p.second;
color[p.second] = 1;
break;
}
}
ret.emplace_back(1, 1);
return ret;
}
// 解説の「貪欲による解法2」を採用
// https://yukicoder.me/problems/no/5007/editorial
vpii terryInit(vpii &cd) {
const ll INF = 1e18;
vvl G(N, vl(N, INF));
auto calDist = [](int x1, int y1, int x2, int y2) {
return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
rep(i, N) rep(j, i) {
G[i][j] = G[j][i] = A * A * calDist(a[i], b[i], a[j], b[j]);
}
vvl dirctG = G;
auto floyd = [&] {
rep(i, N) G[i][i] = 0;
rep(k, N) rep(i, N) {
if (G[i][k] == INF) continue;
rep(j, N) {
if (G[k][j] == INF) continue;
chmin(G[i][j], G[i][k] + G[k][j]);
}
}
};
floyd();
vpii ret;
// 経路復元できるダイクストラ
auto dijkstra = [&](int now, int nexV) {
vl dist(N, INFTY);
vi prev(N, -1);
priority_queue<pii, vpii, greater<pii>> pq;
pq.emplace(0, now);
dist[now] = 0;
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int from = p.second;
if (dist[from] < p.first) continue;
rep(to, N) {
if (chmin(dist[to], dist[from] + dirctG[from][to])) {
prev[to] = from;
pq.emplace(dist[to], to);
}
}
}
// 経路復元する
int current = nexV;
stack<pii> nowToNexRev;
while (current != now) {
nowToNexRev.emplace(1, current + 1);
current = prev[current];
}
while (!nowToNexRev.empty()) {
ret.push_back(nowToNexRev.top());
nowToNexRev.pop();
}
};
vi color(N);
int now = 0;
color[0] = 1;
ret.emplace_back(1, 1);
rep(i, N - 1) {
// 未訪問で1番近い頂点を見つける
ll nexD = INF;
int nexV = -1;
rep(j, N) {
if (color[j]) continue;
if (chmin(nexD, G[now][j])) nexV = j;
}
// ダイクストラして経路復元
dijkstra(now, nexV);
//
now = nexV;
color[nexV] = 1;
}
// 最終地点から1までもダイクストラ
dijkstra(now, 0);
return ret;
}
// 宇宙ステーションの初期配置
vpii initStation() {
vpii ret;
ret.emplace_back(800, 500);
ret.emplace_back(200, 500);
ret.emplace_back(500, 800);
ret.emplace_back(500, 200);
ret.emplace_back(600, 600);
ret.emplace_back(600, 400);
ret.emplace_back(400, 600);
ret.emplace_back(400, 400);
return ret;
}
// シンプルなスコア計算
ll calcScore(vpii &tr) {
ll ret = 0;
int len = (int)tr.size();
auto dist = [](int x1, int y1, int x2, int y2) {
return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
rep(i, len - 1) {
if (tr[i].first == 1 && tr[i + 1].first == 1) {
int x1 = a[tr[i].second - 1];
int y1 = b[tr[i].second - 1];
int x2 = a[tr[i + 1].second - 1];
int y2 = b[tr[i + 1].second - 1];
ret += A * A * dist(x1, y1, x2, y2);
} else if (tr[i].first == 2 && tr[i + 1].first == 2) {
// TODO
} else {
// TODO
}
}
return ret;
}
void solve() {
/* 時間計測 */
auto startClock = system_clock::now();
/* input */
cin >> N >> M;
a.resize(N);
b.resize(N);
rep(i, N) cin >> a[i] >> b[i];
/* solve */
// 初期設定
vpii cd = initStation();
// 前から並べるだけの出力確認
// vpii tr = stupidInit();
// ステーションを経由しない貪欲
// vpii tr = greedyInit();
// ステーションを経由する貪欲
// vpii tr = greedyInit2(cd);
// 解説の「貪欲法による解法（その2）」を再現
// ワーフロして経路復元ダイクストラ
vpii tr = terryInit(cd);
// debug(calcScore(tr));
auto maxScore = calcScore(tr);
/* 焼きなまし法 */
const static double START_TEMP = 1500; // 開始時の温度
const static double END_TEMP = 100; // 終了時の温度
const static double END_TIME = 0.9; // 終了時間（秒）
double time = 0.0; // 経過時間（秒）
// ループ回数のデバッグ用
ll cnt = 0;
do {
break; // 初期値確認
cnt++;
// 進捗。開始時が0.0で、終了時が1.0
const double progressRatio = time / END_TIME;
const double temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;
// 初挑戦
// バックアップ
vpii oldCd = cd;
// ランダム変更
int d = randXor() % 8;
int dx = randXor() % 100;
int dy = randXor() % 100;
cd[d].first = (cd[d].first + dx) % 1000;
cd[d].second = (cd[d].second + dy) % 1000;
// スコア計算
vpii nowTr = greedyInit2(cd);
double nowScore = calcScore(nowTr);
debug(nowScore, maxScore);
if (nowScore <= maxScore) {
maxScore = nowScore;
tr.clear();
tr = nowTr;
} else {
cd = oldCd;
}
// 時間更新
time =
((double)duration_cast<microseconds>(system_clock::now() - startClock)
.count() *
1e-6);
} while (time < END_TIME);
/* output */
debug(cnt);
int V = (int)tr.size();
assert(tr[0].second == 1);
assert(tr[V - 1].second == 1);
rep(i, M) cout << cd[i].first << " " << cd[i].second << "\n";
cout << V << endl;
rep(i, V) cout << tr[i].first << " " << tr[i].second << "\n";
}
};
int main() {
int ts = 1;
rep(ti, ts) {
Solver solver;
solver.solve();
}
return 0;
}