結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー sash2104
提出日時 2022-07-30 14:37:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,563 bytes
コンパイル時間 1,452 ms
実行使用メモリ 4,740 KB
スコア 0
最終ジャッジ日時 2022-07-30 14:38:37
合計ジャッジ時間 38,126 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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];
Pos cps[M];

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);
  }
  // calc center
  REP(i,M) {
    cps[i] = calcCenter(i);
  }
  D1(cps);
}


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) {
      cerr << cps[i].x << " " << cps[i].y << endl;
    }
    cerr << N+1 << endl;
    REP(i,N) {
      cerr << 1 << " " << i+1 << endl;
    }
    cerr << 1 << " " << 1 << 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);
        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();
}
0