結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 kens
|
| 提出日時 | 2022-07-30 17:06:54 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 953 ms / 1,000 ms |
| コード長 | 5,976 bytes |
| コンパイル時間 | 4,486 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 8,885,809 |
| 最終ジャッジ日時 | 2022-07-30 17:07:32 |
| 合計ジャッジ時間 | 35,614 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
using P = pair<ll,ll>;
constexpr int N = 100;
constexpr int M = 8;
constexpr ll A = 5;
constexpr int time_limit = 950;
constexpr ll INF = 1e9;
// simulated annealing
constexpr double temp_start = 1.0;
constexpr double temp_end = 0.0001;
constexpr int climb_loop = 1e7;
ll a[N], b[N];
// random
int seed = 12345;
mt19937 eng(seed);
uniform_real_distribution<> uniform_01;
// timer
class Timer {
private:
chrono::system_clock::time_point start;
public:
Timer() {
start = chrono::system_clock::now();
}
int get_ms() {
auto end = chrono::system_clock::now();
auto t = chrono::duration_cast<chrono::milliseconds>(end-start).count();
return t;
}
};
vector<P> clustering() {
vector<P> point;
rep(i,N) point.push_back(P(a[i],b[i]));
while(point.size() > M) {
int psz = point.size();
ll dm = INF; int p1 = -1, p2 = -1;
rep(i,psz) for(int j = i+1; j < psz; j++) {
ll dx = point[i].first-point[j].first;
ll dy = point[i].second-point[j].second;
ll dist = dx*dx + dy*dy;
if(dist < dm) {
dm = dist;
p1 = i;
p2 = j;
}
}
vector<P> point_new;
rep(i,psz) if(i != p1 and i != p2) point_new.push_back(point[i]);
point_new.push_back(P((point[p1].first+point[p2].first)/2,(point[p1].second+point[p2].second)/2));
swap(point,point_new);
}
return point;
}
void solve() {
Timer timer;
// input
int hello;
cin >> hello >> hello;
rep(i,N) cin >> a[i] >> b[i];
vector<vector<ll>> dpp(N,vector<ll>(N));
rep(i,N) rep(j,N) {
ll dx = a[i]-a[j], dy = b[i]-b[j];
dpp[i][j] = dx*dx + dy*dy;
}
// clustering
vector<P> pg = clustering();
vector<vector<ll>> dpm(N,vector<ll>(M));
rep(i,N) rep(j,M) {
ll dx = a[i]-pg[j].first, dy = b[i]-pg[j].second;
dpm[i][j] = dx*dx + dy*dy;
}
vector<vector<ll>> dmm(M,vector<ll>(M));
rep(i,M) rep(j,M) {
ll dx = pg[i].first-pg[j].first, dy = pg[i].second-pg[j].second;
dmm[i][j] = dx*dx + dy*dy;
}
vector<int> seq(N+1);
rep(i,N) seq[i] = i;
seq[N] = 0;
ll score = 0;
for(int u = 1; u <= N; u++) score += dpp[seq[u]][seq[u-1]]*A*A;
// best sequence
ll best_score = score;
vector<int> best_seq = seq;
auto calc_dist = [&](int u, int v) -> ll {
ll res = dpp[u][v]*A*A;
// via one station
rep(j,M) {
ll d1 = dpm[u][j]*A + dpm[v][j]*A;
if(d1 < res) res = d1;
}
// vis two station
rep(j,M) rep(k,M) {
ll d2 = dpm[u][j]*A + dmm[j][k] + dpm[v][k]*A;
if(d2 < res) res = d2;
}
return res;
};
constexpr int MAX = 30;
constexpr int MOD = 2*MAX+1;
constexpr int PROP = 20;
auto update_dpm = [&](int s) {
rep(i,N) {
ll dx = a[i]-pg[s].first, dy = b[i]-pg[s].second;
dpm[i][s] = dx*dx + dy*dy;
}
};
auto update_dmm = [&](int s) {
rep(i,M) {
ll dx = pg[i].first-pg[s].first, dy = pg[i].second-pg[s].second;
dmm[i][s] = dx*dx + dy*dy;
dmm[s][i] = dx*dx + dy*dy;
}
};
int last = 0;
// two opt with clustering + move cluster point
rep(cn,climb_loop) {
if(timer.get_ms() > time_limit) break;
double temp = temp_start + (temp_end - temp_start)*cn/climb_loop;
int id = eng() % PROP;
if(id) {
// 経路変更
int s = eng() % (N-1) + 1;
int t = eng() % (N-1) + 1;
if(s == t) continue;
if(s > t) swap(s,t);
ll score_diff = calc_dist(seq[t],seq[s-1]) + calc_dist(seq[s],seq[t+1]) - calc_dist(seq[s],seq[s-1]) - calc_dist(seq[t],seq[t+1]);
if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
score += score_diff;
reverse(seq.begin()+s,seq.begin()+t+1);
}
} else {
// 位置変更
int dx = (eng() % MOD) - MAX;
int dy = (eng() % MOD) - MAX;
if(dx == 0 and dy == 0) continue;
int s = eng() % M;
pg[s].first += dx; pg[s].second += dy;
update_dpm(s);
update_dmm(s);
ll score_new = 0;
for(int i = 1; i <= N; i++) score_new += calc_dist(seq[i-1],seq[i]);
ll score_diff = score_new - score;
if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
score += score_diff;
} else {
pg[s].first -= dx; pg[s].second -= dy;
update_dpm(s);
update_dmm(s);
}
}
if(score < best_score) {
last = timer.get_ms();
best_score = score;
best_seq = seq;
}
}
// 復元
ll score_cluster = 0;
vector<P> seq_cluster;
seq_cluster.push_back(P(1,0));
// consider clustering
for(int i = 1; i <= N; i++) {
ll res = dpp[best_seq[i]][best_seq[i-1]]*A*A;
ll s1 = -1, s2 = -1;
// via one station
rep(j,M) {
ll d1 = dpm[best_seq[i-1]][j]*A + dpm[best_seq[i]][j]*A;
if(d1 < res) {
res = d1;
s1 = j;
}
}
// vis two station
rep(j,M) rep(k,M) {
ll d2 = dpm[best_seq[i-1]][j]*A + dmm[j][k] + dpm[best_seq[i]][k]*A;
if(d2 < res) {
res = d2;
s1 = j; s2 = k;
}
}
score_cluster += res;
if(s1 == -1 and s2 == -1) {
seq_cluster.push_back(P(1,best_seq[i]));
} else if(s1 != -1 and s2 == -1) {
seq_cluster.push_back(P(2,s1));
seq_cluster.push_back(P(1,best_seq[i]));
} else {
seq_cluster.push_back(P(2,s1));
seq_cluster.push_back(P(2,s2));
seq_cluster.push_back(P(1,best_seq[i]));
}
}
int final_score = round(1e9/(1000.0+sqrt((double)score_cluster)));
// cerr << best_score << endl;
cerr << "Time " << timer.get_ms() << endl;
cerr << "Score = " << final_score << endl;
rep(i,M) cout << pg[i].first << " " << pg[i].second << endl;
cout << seq_cluster.size() << endl;
for(auto [t, v] : seq_cluster) cout << t << " " << v+1 << endl;
}
int main() {
solve();
return 0;
}