結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 sash2104
|
| 提出日時 | 2022-07-30 15:59:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 806 ms / 1,000 ms |
| コード長 | 11,610 bytes |
| コンパイル時間 | 1,981 ms |
| 実行使用メモリ | 5,160 KB |
| スコア | 7,980,251 |
| 最終ジャッジ日時 | 2022-07-30 15:59:50 |
| 合計ジャッジ時間 | 28,716 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
// Debug
template<class T>
void print_collection(std::ostream& out, T const& x);
template<class A>
std::ostream& operator<<(std::ostream& out, std::vector<A> const& x) { print_collection(out, x); return out; }
template<class A, size_t N>
std::ostream& operator<<(std::ostream& out, std::array<A, N> const& x) { print_collection(out, x); return out; }
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>);
template<class... A>
std::ostream& operator<<(std::ostream& out, std::tuple<A...> const& x) {
print_tuple(out, x, std::index_sequence_for<A...>{});
return out;
}
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>){
using swallow = int[];
out << '(';
(void)swallow{0, (void(out << (I == 0? "" : ", ") << std::get<I>(a)), 0)...};
out << ')';
}
template<class T>
void print_collection(std::ostream& out, T const& x) {
int f = 0;
out << '[';
for(auto const& i: x) {
out << (f++ ? "," : "");
out << i;
}
out << "]";
}
static inline void d1_impl_seq() { std::cerr << "}"; }
template <class T, class... V>
void d1_impl_seq(T const& t, V const&... v) {
std::cerr << t;
if(sizeof...(v)) { std::cerr << ", "; }
d1_impl_seq(v...);
}
static inline void d2_impl_seq() { }
template <class T, class... V>
void d2_impl_seq(T const& t, V const&... v) {
std::cerr << " " << t;
d2_impl_seq(v...);
}
#define D0(x) do { std::cerr << __FILE__ ":" << __LINE__ << ":" << __func__ << " " << x << std::endl; } while (0)
#define D1(x...) do { \
std::cerr << __LINE__ << " {" << #x << "} = {"; \
d1_impl_seq(x); \
std::cerr << std::endl << std::flush; \
} while(0)
#define D2(x...) do { \
std::cerr << "!"; \
d2_impl_seq(x); \
std::cerr << std::endl << std::flush; \
} while(0)
using namespace std;
static constexpr int INF = 1<<30;
// #define NDEBUG
static std::vector<std::string> split(const std::string &s, char delim) {
std::vector<std::string> elems;
std::stringstream ss(s);
std::string item;
while (getline(ss, item, delim)) {
if (!item.empty()) {
elems.push_back(item);
}
}
return elems;
}
struct XorShift {
unsigned int x, y, z, w;
double nL[65536];
XorShift() { init(); }
void init()
{
x = 314159265; y = 358979323; z = 846264338; w = 327950288;
double n = 1 / (double)(2 * 65536);
for (int i = 0; i < 65536; i++) {
nL[i] = log(((double)i / 65536) + n);
}
}
inline unsigned int next() { unsigned int t=x^x<<11; x=y; y=z; z=w; return w=w^w>>19^t^t>>8; }
inline double nextLog() { return nL[next()&0xFFFF]; }
inline int nextInt(int m) { return (int)(next()%m); } // [0, m)
int nextInt(int min, int max) { return min+nextInt(max-min+1); } // [min, max]
inline double nextDouble() { return (double)next()/((long long)1<<32); } // [0, 1]
};
XorShift rng;
template <typename T>
inline void rough_shuffle(vector<T>& lv) {
int n = lv.size();
for (int i = n; i > 0; --i) {
int id = rng.nextInt(i);
swap(lv[id], lv[i-1]);
}
}
std::size_t calc_hash(std::vector<int> const& vec) {
std::size_t seed = vec.size();
for(auto& i : vec) {
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
struct Timer {
const double LIMIT; // FIXME: 時間制限(s)
Timer() : LIMIT(0.95) { reset(); }
Timer(double limit) : LIMIT(limit) { reset(); }
chrono::system_clock::time_point start;
void reset() {
start = chrono::system_clock::now();
}
double get() {
auto end = chrono::system_clock::now();
return chrono::duration_cast<chrono::milliseconds>(end - start).count()/1000.0;
}
};
// ------------- Constants ------------
constexpr int N = 100;
constexpr int M = 8;
constexpr int A = 5; // alpha
constexpr int AA = 25; // alpha*alpha
int dist_[N][N];
struct Pos {
int x = -1, y = -1, c = -1;
Pos() {}
Pos(int x, int y): x(x), y(y) {}
bool operator == (const Pos &other) const {
return (other.x == x) && (other.y == y);
}
bool operator != (const Pos &other) const {
return !((*this) == other);
}
int distance(const Pos &other) const {
return (x-other.x)*(x-other.x)+(y-other.y)*(y-other.y);
}
int id2() const { return y*N+x; }
friend std::ostream& operator<<(std::ostream& os, const Pos &p) {
os << "(" << p.x << "," << p.y << ")";
return os;
}
};
Pos ps[N];
vector<Pos> cps(M);
vector<int> bestRoute; // cpsのめぐる順
Pos calcCenter(int cid) {
int sx = 0, sy = 0;
int n = 0;
REP(i,N) {
if (ps[i].c != cid) continue;
sx += ps[i].x;
sy += ps[i].y;
++n;
}
if (n == 0) return Pos(rng.nextInt(1000), rng.nextInt(1000));
assert(n > 0);
return Pos(sx/n, sy/n);
}
void kmeans() {
// init
REP(i,N) {
ps[i].c = rng.nextInt(M);
}
int nUpdate = 0;
REP(t,100) {
// calc center
REP(i,M) {
cps[i] = calcCenter(i);
}
// assign center
bool update = false;
REP(i,N) {
int bj = -1;
int best = INF;
REP(j,M) {
int d = ps[i].distance(cps[j]);
if (d < best) {
bj = j;
best = d;
}
}
assert(bj != -1);
if (ps[i].c != bj) {
update = true;
}
ps[i].c = bj;
}
nUpdate = t;
if (!update) break;
}
D1(nUpdate, cps);
}
// center同士の訪れ方
vector<bool> visit(M);
int bestRouteScore = INF;
void dfs(int cur, int sumd, vector<int> &route) {
if (route.size() == M) {
int d = cps[route[M-1]].distance(cps[route[0]]);
int score = sumd+d;
if (score < bestRouteScore) {
bestRoute = route;
bestRouteScore = score;
}
return;
}
visit[cur] = true;
REP(i,M) {
if (visit[i]) continue;
int d = cps[cur].distance(cps[i]);
route.push_back(i);
dfs(i, sumd+d, route);
route.pop_back();
}
visit[cur] = false;
}
struct State {
int score = 0;
int btype = 0;
int bi, bj, bscore;
vector<int> route;
State() {}
State(vector<int> &r): route(r) {
score = calcScore();
}
int update(double progress) {
int n = route.size();
int i = rng.nextInt(1, n-1);
int j = rng.nextInt(1, n-2);
if (j >= i) ++j;
assert(i != j);
if (i > j) swap(i,j);
bi = i;
bj = j;
bscore = score;
int ci = i, cj = j;
assert(ci < cj);
while (ci < cj) {
swap(route[ci++], route[cj--]);
}
score = calcScore();
// if (score < bscore) {
// D1(bscore, score);
// }
return bscore-score;
}
int calcScore() {
int ret = 0;
REP(i,route.size()-1) {
// assert(route[i] < N);
// assert(route[i+1] < N);
ret += dist_[route[i]][route[i+1]];
}
assert(route.size() > 0);
ret += dist_[route[route.size()-1]][route[0]];
return ret;
}
void revert() {
int ci = bi, cj = bj;
assert(ci < cj);
while (ci < cj) {
swap(route[ci++], route[cj--]);
}
score = bscore;
}
void revert1() {
}
void write() {
} // write current solution
};
vector<State> bstates;
void initState(State &s) {
s.score = s.calcScore();
}
struct SASolver {
double startTemp = 30;
double endTemp = 0.001;
// Timer timer = Timer(2.85);
Timer timer = Timer(0.1);
// Timer timer = Timer(200);
State best;
SASolver() { init(); }
SASolver(double st, double et): startTemp(st), endTemp(et) { init(); }
SASolver(double st, double et, double limit): startTemp(st), endTemp(et), timer(limit) { init(); }
void init() {} // 初期化処理をここに書く
void solve(State &state) {
double t;
best = state;
int step = 0;
vector<int> total(6);
vector<int> ac(6);
// best.write();
while ((t = timer.get()) < timer.LIMIT) // 焼きなまし終了時刻までループ
{
double T = startTemp + (endTemp - startTemp) * t / timer.LIMIT;
double progress = t/timer.LIMIT;
// assert(0 <= progress && progress <= 1);
for (int i = 0; i < 100; ++i) { // 時間計算を間引く
double diff = state.update(progress);
total[state.btype]++;
if (diff <= -INF+0.1) {
state.revert();
continue;
}
// 最初t=0のときは、スコアが良くなろうが悪くなろうが、常に次状態を使用
// 最後t=timer.LIMITのときは、スコアが改善したときのみ、次状態を使用
// スコアが良くなった or 悪くなっても強制遷移
double tr = T*rng.nextLog();
// cerr << t << " " << T << " " << tr << " " << diff << endl;
if (diff >= tr)
{
ac[state.btype]++;
if (best.score > state.score) {
best = state;
// D1(t, step, best.score);
// best.write();
}
}
else { state.revert(); }
++step;
}
}
D1(step, best.score);
REP3(i,1,6) {
if (total[i] == 0) continue;
cerr << i << ":" << 1.0*ac[i]/total[i] << "(" << ac[i] << "/" << total[i] << ")" << endl;
}
}
};
struct Solver {
Solver() {
reset();
}
void reset() {
}
void solve() {
State state; // 開始状態
vector<int> route = {ps[0].c};
dfs(ps[0].c, 0, route);
D1(bestRouteScore, bestRoute);
REP(i,M) {
vector<int> subRoute;
REP(j,N) {
if (ps[j].c == bestRoute[i]) subRoute.push_back(j);
}
D1(i, subRoute);
State s(subRoute);
SASolver sa;
sa.solve(s);
D1(i, sa.best.route);
bstates.emplace_back(sa.best);
}
state.write();
// SASolver s;
// s.solve(state);
// s.best.write();
// show(s.best.grid);
// float score = s.best.calcScore();
// D1(score);
}
void readInput() {
int n_, m_;
cin >> n_ >> m_;
REP(i,N) {
int x, y; cin >> x >> y;
ps[i] = Pos(x,y);
}
}
void writeOutput() {
REP(i,M) {
cout << cps[i].x << " " << cps[i].y << endl;
}
vector<pair<int,int>> out;
REP(i,M) {
int c = bestRoute[i];
if (i > 0) out.emplace_back(2, c+1);
if (i == 0) {
assert(ps[0].c == c);
}
State &s = bstates[i];
REP(k, s.route.size()-1) {
int v1 = s.route[k];
int v2 = s.route[k+1];
int d1 = dist_[v1][v2];
int d2 = ps[v1].distance(cps[c])+ps[v2].distance(cps[c]);
out.emplace_back(1, v1+1);
if (d1*A > d2) {
out.emplace_back(2, c+1);
}
}
out.emplace_back(1, s.route.back()+1);
out.emplace_back(2, c+1);
}
out.emplace_back(2, bestRoute[0]+1);
out.emplace_back(1, 1);
cout << out.size() << endl;
for (auto it: out) {
cout << it.first << " " << it.second << endl;
}
}
};
void initPos() {
REP(i,N) REP(j,N) dist_[i][j] = ps[i].distance(ps[j]);
}
int main()
{
Solver solver;
solver.readInput();
initPos();
kmeans();
solver.solve();
solver.writeOutput();
}