結果

問題 No.5007 Steiner Space Travel
ユーザー qLethon
提出日時 2022-07-30 15:02:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 503 ms / 1,000 ms
コード長 10,227 bytes
コンパイル時間 2,864 ms
実行使用メモリ 3,848 KB
スコア 4,769,099
最終ジャッジ日時 2022-07-30 15:03:10
合計ジャッジ時間 20,205 ms
ジャッジサーバーID
(参考情報)
judge10 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
u_int64_t seed = 91;
u_int64_t xor_shift(){
seed ^= seed << 1;
seed ^= seed >> 3;
seed ^= seed << 10;
return seed;
}
class Time{
public:
chrono::system_clock::time_point start_time;
Time(){
start_time = now();
}
chrono::system_clock::time_point now(){
return chrono::system_clock::now();
}
int elapsed(){
auto cur = chrono::system_clock::now();
return chrono::duration_cast<chrono::milliseconds>(cur - start_time).count();
}
};
template <class T>
class TSP{
vector<vector<T>> D;
vector<int> ans, A, v_to_cycle;
vector<vector<int>> nearest;
int n;
T INF;
public:
TSP (vector<vector<T>> D, T INF): D(D), n(D.size()), INF(INF){
ans.resize(n);
iota(ans.begin(), ans.end(), 0);
v_to_cycle.resize(n);
iota(v_to_cycle.begin(), v_to_cycle.end(), 0);
A.resize(n);
iota(A.begin(), A.end(), 0);
nearest.assign(n, vector<int>(n));
for (int i = 0; i < n; i++){
vector<pair<T, int>> B(n);
for (int j = 0; j < n; j++)
B[j] = {D[i][j], j};
sort(B.begin(), B.end());
for (int j = 0; j < n; j++)
nearest[i][j] = B[j].second;
}
};
vector<int> solve_perm(){
vector<int> P(n);
iota(P.begin(), P.end(), 0);
T best_score = INF;
vector<int> best = P;
do {
T s = calc_score(P);
if (s < best_score){
best = P;
best_score = s;
}
} while (next_permutation(P.begin(), P.end()));
return best;
}
vector<int> solve(int time_limit){
if (n < 10)
return solve_perm();
Time time;
// // initial 2-opt
// while (true){
// bool updated = false;
// for (int t1 = 0; t1 < n; t1++){
// int t2 = (t1 + 1) % n;
// for (const auto &v: nearest[ans[t2]]){
// int t3 = v_to_cycle[v];
// if (dist(t1, t2) <= dist(t2, t3))
// break;
// int t4 = (t3 - 1 + n) % n;
// int i, j;
// if (t2 <= t4)
// tie(i, j) = {t2, t4};
// else
// tie(i, j) = {t3, t1};
// const auto d = calc_two_opt_score(i, j);
// if (d < 0){
// two_opt_swap(i, j);
// updated = true;
// }
// }
// }
// if (!updated)
// break;
// }
// kick (double bridge + 2-opt)
auto best = ans;
auto best_v_to_cycle = v_to_cycle;
T score = calc_score(ans);
int loop = 0;
while (time.elapsed() < time_limit){
loop++;
ans = best;
v_to_cycle = best_v_to_cycle;
// kick
T diff = 0;
{
auto chosen = choose_k(4);
sort(chosen.begin(), chosen.end());
diff = calc_double_bridge(chosen[0], chosen[1], chosen[2], chosen[3]);
double_birdge(chosen[0], chosen[1], chosen[2], chosen[3]);
}
// // random 2-opt
// for (int i = 0; i < 6; i++){
// const int a = xor_shift() % n;
// const int b = xor_shift() % n;
// diff += calc_two_opt_score(a, b);
// two_opt_swap(a, b);
// }
vector<int> Q(n);
iota(Q.begin(), Q.end(), 0);
// local optimization
while (true){
bool updated = false;
vector<int> NQ;
for (auto u: Q){
int t1 = v_to_cycle[u];
int t2 = (t1 + 1) % n;
for (const auto &v: nearest[ans[t2]]){
int t3 = v_to_cycle[v];
if (dist(t1, t2) <= dist(t2, t3))
break;
int t4 = (t3 - 1 + n) % n;
int i, j;
if (t2 <= t4)
tie(i, j) = {t2, t4};
else
tie(i, j) = {t3, t1};
const auto d = calc_two_opt_score(i, j);
if (d < 0){
NQ.push_back(ans[(t1 - 1 + n) % n]);
NQ.push_back(ans[t1]);
NQ.push_back(ans[t2]);
NQ.push_back(ans[(t2 + 1) % n]);
NQ.push_back(ans[(t4 - 1 + n) % n]);
NQ.push_back(ans[t3]);
NQ.push_back(ans[t4]);
NQ.push_back(ans[(t3 + 1) % n]);
two_opt_swap(i, j);
diff += d;
updated = true;
break;
}
}
}
if (!updated)
break;
Q = NQ;
sort(Q.begin(), Q.end());
Q.erase(unique(Q.begin(), Q.end()), Q.end());
}
if (diff < 0){
best = ans;
best_v_to_cycle = v_to_cycle;
score += diff;
cerr << score << endl;
}
}
cerr << "loop: " << loop << endl;
// cerr << score << endl;
return best;
}
T dist(int i, int j){
// %n
if (i < 0)
i += n;
if (i >= n)
i -= n;
if (j < 0)
j += n;
if (j >= n)
j -= n;
return D[ans[i]][ans[j]];
}
T dist(int i, int j, const vector<int> &ans){
return D[ans[i]][ans[j]];
}
T calc_score(const vector<int> &ans){
T res = 0;
assert(ans.size() > 0);
for (int i = 0; i < ans.size() - 1; i++)
res += dist(i, i + 1, ans);
res += dist(ans.size() - 1, 0, ans);
return res;
}
T calc_two_opt_score(int i, int j){
T res = 0;
if (i > j)
swap(i, j);
if (i == 0 and j == n - 1)
return 0;
res += dist((i - 1 + n) % n, j) - dist((i - 1 + n) % n, i);
res += dist(i, (j + 1) % n) - dist(j, (j + 1) % n);
return res;
}
void two_opt_swap(int i, int j){
if (i > j)
swap(i, j);
reverse(ans.begin() + i, ans.begin() + j + 1);
for (int a = i; a <= j; a++)
v_to_cycle[ans[a]] = a;
}
T three_opt_swap(int i, int j, int k){
assert(i < j and j < k);
array<T, 5> d;
i--; j--; k--; //
d[0] = dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1);
d[1] = dist(i, j) + dist(i + 1, j + 1) + dist(k, k + 1);
d[2] = dist(i, i + 1) + dist(j, k) + dist(j + 1, k + 1);
d[3] = dist(i, j + 1) + dist(k, i + 1) + dist(j, k + 1);
d[4] = dist(k + 1, i + 1) + dist(j, j + 1) + dist(k, i);
i++; j++; k++;
if (d[0] > d[1]){
reverse(ans.begin() + i, ans.begin() + j);
return -d[0] + d[1];
} else if (d[0] > d[2]){
reverse(ans.begin() + j, ans.begin() + k);
return -d[0] + d[2];
} else if (d[0] > d[4]){
reverse(ans.begin() + i, ans.begin() + k);
return -d[0] + d[4];
} else if (d[0] > d[3]){
vector<int> tmp(k - i);
copy(ans.begin() + j, ans.begin() + k, tmp.begin());
copy(ans.begin() + i, ans.begin() + j, tmp.begin() + k - j);
copy(tmp.begin(), tmp.end(), ans.begin() + i);
return -d[0] + d[3];
}
return 0;
}
T calc_double_bridge(int i, int j, int k, int l){
assert(i < j and j < k and k < l);
T res = 0;
res -= dist(i, i + 1) + dist(j, j + 1) + dist(k, k + 1) + dist(l, (l + 1) % n);
res += dist(i, k + 1) + dist(j, (l + 1) % n) + dist(k, i + 1) + dist(l, j + 1);
return res;
}
void double_birdge(int i, int j, int k, int l){
assert(i < j and j < k and k < l);
assert(l < n);
vector<int> res(n);
copy(ans.begin(), ans.begin() + i + 1, res.begin());
copy(ans.begin() + k + 1, ans.begin() + l + 1, res.begin() + i + 1);
copy(ans.begin() + j + 1, ans.begin() + k + 1, res.begin() + i + l - k + 1);
copy(ans.begin() + i + 1, ans.begin() + j + 1, res.begin() + i + l - j + 1);
copy(ans.begin() + l + 1, ans.end(), res.begin() + l + 1);
ans = res;
for (int a = 0; a < n; a++)
v_to_cycle[ans[a]] = a;
}
vector<int> choose_k(int k){
const int m = A.size();
assert(k <= m);
vector<int> res(k);
for (int i = 0; i < k; i++){
int r = i + xor_shift() % (m - i);
swap(A[i], A[r]);
res[i] = A[i];
}
return res;
}
};
int main(){
int n, m;
cin >> n >> m;
vector<int> A(n), B(n);
for (int i = 0; i < n; i++)
cin >> A[i] >> B[i];
constexpr int alpha = 5;
vector<vector<int64_t>> D(n, vector<int64_t>(n));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
D[i][j] = (A[i] - A[j]) * (A[i] - A[j]) + (B[i] - B[j]) * (B[i] - B[j]) * alpha * alpha;
}
}
TSP tsp(D, int64_t(1e15));
auto ans = tsp.solve(500);
cerr << tsp.calc_score(ans) << endl;
for (int i = 0; i < m; i++)
cout << "0 0" << endl;
for (int i = 0; i < n; i++){
if (ans[i] == 0)
rotate(ans.begin(), ans.begin() + i, ans.end());
}
assert(ans[0] == 0);
cout << n + 1 << endl;
for (const auto &a: ans)
cout << "1 " << a + 1 << endl;
cout << "1 1" << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0