結果

問題 No.5007 Steiner Space Travel
ユーザー sash2104
提出日時 2022-07-30 15:03:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 1,000 ms
コード長 9,935 bytes
コンパイル時間 1,746 ms
実行使用メモリ 5,164 KB
スコア 6,916,319
最終ジャッジ日時 2022-07-30 15:03:55
合計ジャッジ時間 3,843 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

#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);
}
REP(t,100) {
// calc center
REP(i,M) {
cps[i] = calcCenter(i);
}
D1(cps);
// assign center
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);
ps[i].c = bj;
}
}
}
// 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 {
double score = 0;
int btype = 0;
State(){
}
double update(double progress) {
return 0;
}
int calcScore() {
int ret = 0;
return ret;
}
void revert() {
// if (btype == 1) revert1();
// else if (btype == 2) revert2();
// else if (btype == 3) revert3();
}
void revert1() {
}
void write() {
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);
}
REP(j,N) {
if (ps[j].c != c) continue;
out.emplace_back(1, j+1);
out.emplace_back(2, c+1);
}
}
out.emplace_back(1, 1);
cout << out.size() << endl;
for (auto it: out) {
cout << it.first << " " << it.second << endl;
}
} // write current solution
};
void initState(State &s) {
s.score = s.calcScore();
}
struct SASolver {
double startTemp = 3;
double endTemp = 0.001;
// Timer timer = Timer(2.85);
Timer timer = Timer(0.85);
// 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; //
initState(state);
vector<int> route = {ps[0].c};
dfs(ps[0].c, 0, route);
D1(bestRouteScore, bestRoute);
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 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0