#783051 (C++14) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	sash2104
提出日時	2022-07-30 15:59:15
言語	C++14 (gcc 12.3.0 + boost 1.83.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
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	806 ms 4,900 KB
testcase_01	AC	805 ms 5,156 KB
testcase_02	AC	805 ms 4,900 KB
testcase_03	AC	805 ms 4,900 KB
testcase_04	AC	805 ms 5,160 KB
testcase_05	AC	805 ms 4,904 KB
testcase_06	AC	805 ms 4,904 KB
testcase_07	AC	806 ms 4,904 KB
testcase_08	AC	805 ms 4,900 KB
testcase_09	AC	805 ms 4,904 KB
testcase_10	AC	804 ms 4,900 KB
testcase_11	AC	805 ms 4,900 KB
testcase_12	AC	805 ms 5,156 KB
testcase_13	AC	805 ms 4,900 KB
testcase_14	AC	804 ms 4,900 KB
testcase_15	AC	805 ms 4,900 KB
testcase_16	AC	805 ms 4,904 KB
testcase_17	AC	805 ms 4,368 KB
testcase_18	AC	805 ms 5,160 KB
testcase_19	AC	805 ms 4,900 KB
testcase_20	AC	805 ms 5,156 KB
testcase_21	AC	805 ms 5,156 KB
testcase_22	AC	805 ms 4,904 KB
testcase_23	AC	805 ms 4,900 KB
testcase_24	AC	805 ms 4,900 KB
testcase_25	AC	804 ms 5,160 KB
testcase_26	AC	805 ms 5,160 KB
testcase_27	AC	805 ms 4,904 KB
testcase_28	AC	804 ms 4,900 KB
testcase_29	AC	806 ms 4,908 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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();
}

yukicoder

結果

テストケース

ソースコード