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

• 問題: No.5007 Steiner Space Travel
• ユーザー: どらら
• 提出日時: 2022-07-30 16:41:35
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 984 ms / 1,000 ms
• コード長: 7,549 bytes
• コンパイル時間: 5,032 ms
• 実行使用メモリ: 6,952 KB
• スコア: 8,230,982
• 最終ジャッジ日時: 2022-07-30 16:42:12
• 合計ジャッジ時間: 36,362 ms
• ジャッジサーバーID （参考情報）: judge10 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	982 ms; 4,900 KB
testcase_01	AC	983 ms; 4,904 KB
testcase_02	AC	983 ms; 6,952 KB
testcase_03	AC	983 ms; 6,952 KB
testcase_04	AC	982 ms; 6,948 KB
testcase_05	AC	982 ms; 4,904 KB
testcase_06	AC	982 ms; 4,904 KB
testcase_07	AC	983 ms; 6,948 KB
testcase_08	AC	983 ms; 4,900 KB
testcase_09	AC	983 ms; 4,904 KB
testcase_10	AC	983 ms; 6,948 KB
testcase_11	AC	984 ms; 4,900 KB
testcase_12	AC	982 ms; 6,948 KB
testcase_13	AC	983 ms; 6,952 KB
testcase_14	AC	983 ms; 4,904 KB
testcase_15	AC	983 ms; 4,904 KB
testcase_16	AC	982 ms; 4,900 KB
testcase_17	AC	981 ms; 6,952 KB
testcase_18	AC	983 ms; 4,908 KB
testcase_19	AC	983 ms; 6,948 KB
testcase_20	AC	983 ms; 6,948 KB
testcase_21	AC	982 ms; 4,900 KB
testcase_22	AC	982 ms; 6,952 KB
testcase_23	AC	982 ms; 4,904 KB
testcase_24	AC	982 ms; 4,900 KB
testcase_25	AC	983 ms; 4,904 KB
testcase_26	AC	982 ms; 4,908 KB
testcase_27	AC	984 ms; 4,904 KB
testcase_28	AC	982 ms; 4,904 KB
testcase_29	AC	982 ms; 4,904 KB

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
//using mint = modint1000000007;
//using mint = modint998244353;

class Timer {
  std::chrono::system_clock::time_point start_time;
  std::chrono::system_clock::time_point getNow() {
    return std::chrono::system_clock::now();
  }
  
public:
  void start() {
    start_time = getNow();
  }
  float getSec() {
    float count =
      std::chrono::duration_cast<std::chrono::microseconds>(getNow() - start_time).count();
    return count / 1e6;
  }
};

uint32_t xor128() {
  static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
  uint32_t t;
  t = (x ^ (x << 11));
  x = y;
  y = z;
  z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

struct P {
  int t,i;
  double y, x;
  P():t(0),i(0),y(0),x(0){}
  P(int t, int i, double y, double x):t(t),i(i),y(y),x(x){}
};
double distance(const P& a, const P& b) {
  static constexpr double alpha = 5.0;
  
  if(a.t == 1 && b.t == 1){
    return alpha*alpha*((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }
  else if(a.t == 1 || b.t == 1){
    return alpha * ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }
  else{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  }
}


vector<int> kmeans(const vector<P>& p, int M){
  vector<P> r;
  rep(i,M) r.emplace_back(p[i]);
  
  vector<int> ret(p.size());
  //rep(i,ret.size()) ret[i] = i%M;
  rep(i,ret.size()) ret[i] = xor128()%M;
  
  rep(t,1000000){
    bool change = false;
    
    vector<P> g(M);
    rep(i,p.size()){
      g[ret[i]].y += p[i].y;
      g[ret[i]].x += p[i].x;
      g[ret[i]].i++;
    }
    rep(i,M){
      if(g[i].i == 0){
        int r = xor128()%p.size();
        g[i].y = p[r].y;
        g[i].x = p[r].x;
      }else{
        g[i].y /= g[i].i;
        g[i].x /= g[i].i;
      }
    }
    rep(i,p.size()){
      double mind = 1e9;
      int minj = 0;
      rep(j,M){
        double d = distance(p[i],g[j]);
        if(mind > d){
          mind = d;
          minj = j;
        }
      }
      if(ret[i] != minj){
        change = true;
        ret[i] = minj;
      }
    }
    if(!change) break;
  }
  return ret;
}

vector<int> small_tsp(const vector<P>& v){
  int N = v.size();

  double tour_distance = 0;
  vector<int> tour(N);
  for (int i = 0; i < N; i++) {
    tour[i] = i;
    tour_distance += distance(v[tour[i]], v[tour[(i + 1) % N]]);
  }
  double best_distance = tour_distance;
  vector<int> best_tour = tour;
  do {
    tour_distance = 0;
    for (int i = 0; i < N; i++) {
      tour_distance += distance(v[tour[i]], v[tour[(i + 1) % N]]);
    }
    if (best_distance > tour_distance) {
      best_distance = tour_distance;
      best_tour = tour;
    }
  } while (next_permutation(tour.begin(), tour.end()));

  while(best_tour[0] != 0) rotate(best_tour.begin(), best_tour.begin()+1,best_tour.end());
  
  return best_tour;
}

struct ST {
  int i;
  double ox, oy;
  ll x, y;
};
bool operator<(const ST& a, const ST& b){
  int sa = -1;
  if(a.x>=0 && a.y>=0) sa = 1;
  else if(a.x<=0 && a.y>=0) sa = 2;
  else if(a.x<=0 && a.y<=0) sa = 3;
  else if(a.x>=0 && a.y<=0) sa = 4;
  int sb = -1;
  if(b.x>=0 && b.y>=0) sb = 1;
  else if(b.x<=0 && b.y>=0) sb = 2;
  else if(b.x<=0 && b.y<=0) sb = 3;
  else if(b.x>=0 && b.y<=0) sb = 4;

  if(sa != sb) return sa < sb;

  return a.x * b.y - b.x * a.y > 0;
}


int N, M;
vector<P> planets;

ll calc_score(const vector<P>& ss, const vector<pair<int,int>>& ans){
  
  double ret = 0;

  rep(i,ans.size()-1){
    P p1, p2;
    if(ans[i].first == 1) p1 = planets[ans[i].second-1];
    if(ans[i].first == 2) p1 = ss[ans[i].second-1];
    if(ans[i+1].first == 1) p2 = planets[ans[i+1].second-1];
    if(ans[i+1].first == 2) p2 = ss[ans[i+1].second-1];

    ret += distance(p1, p2);
  }
  return (ll)(1e9 / (1000.0 + sqrt(ret)));
}



Timer timer;
static constexpr double TIME_LIMIT = 0.98;

int main(){
  timer.start();
  
  cin >> N >> M;
  rep(i,N){
    ll y, x;
    cin >> y >> x;
    planets.emplace_back(1,i+1,y,x);
  }

  vector<pair<int,int>> best_ans;
  vector<P> best_ss;
  ll best_score = 0;

  while(true){
    double sec = timer.getSec();
    if(sec > TIME_LIMIT) break;
    
    vector<int> cluster = kmeans(planets,M);
    if(sec > TIME_LIMIT) break;
    
    vector<P> ss(M);
    vector<int> ss_num(M,0);
    rep(i,planets.size()){
      ss[cluster[i]].y += planets[i].y;
      ss[cluster[i]].x += planets[i].x;
      ss_num[cluster[i]]++;
    }
    rep(i,M){
      ss[i].t = 2;
      ss[i].i = i+1;
      if(ss_num[i] == 0) continue;
      ss[i].y /= ss_num[i];
      ss[i].x /= ss_num[i];
    }
    
    if(cluster[0] != 0){
      int c = cluster[0];
      rep(i,cluster.size()){
        if(cluster[i] == c) cluster[i] = 0;
        else if(cluster[i] == 0) cluster[i] = c;
      }
      swap(ss[0], ss[c]);
      swap(ss_num[0], ss_num[c]);
      ss[0].i = 1;
      ss[c].i = c+1;
    }

    vector<P> groups[10];
    
    rep(i,planets.size()){
      if(planets[i].i == 1) continue;
      groups[cluster[i]].push_back(planets[i]);
    }
    
    if(sec > TIME_LIMIT) break;
    vector<int> ss_tsp = small_tsp(ss);
    if(sec > TIME_LIMIT) break;
    
    vector<pair<int,int>> ans;
    ans.emplace_back(1,1);
    rep(i,ss_tsp.size()){
      if(ss_num[ss_tsp[i]] == 0) continue;
      ans.emplace_back(2,ss[ss_tsp[i]].i);
      
      vector<ST> sts;
      rep(j,groups[ss_tsp[i]].size()){
        sts.push_back((ST){groups[ss_tsp[i]][j].i,groups[ss_tsp[i]][j].x,groups[ss_tsp[i]][j].y,(ll)(groups[ss_tsp[i]][j].x-ss[ss_tsp[i]].x),(ll)(groups[ss_tsp[i]][j].y-ss[ss_tsp[i]].y)});
      }
      sort(ALLOF(sts));

      if(sts.size() >= 3){
        double mind = 1e9;
        double minj = 0;
        rep(j,sts.size()){
          double d = distance((P){1,0,sts[j].oy,sts[j].ox},(P){2,0,ss[ss_tsp[i]].y,ss[ss_tsp[i]].x}) +
            distance((P){1,0,sts[(j+1)%sts.size()].oy,sts[(j+1)%sts.size()].ox},(P){2,0,ss[ss_tsp[i]].y,ss[ss_tsp[i]].x});
          if(mind > d){
            mind = d;
            minj = (j+1)%sts.size();
          }
        }
        rotate(sts.begin(), sts.begin()+minj, sts.end());
      }
      
      ans.emplace_back(1,sts[0].i);
      rep(j,sts.size()-1){
        double d1 = distance((P){1,0,sts[j].oy,sts[j].ox},(P){1,0,sts[j+1].oy,sts[j+1].ox});
        double d2 = distance((P){1,0,sts[j].oy,sts[j].ox},(P){2,0,ss[ss_tsp[i]].y,ss[ss_tsp[i]].x}) +
          distance((P){2,0,ss[ss_tsp[i]].y,ss[ss_tsp[i]].x},(P){1,0,sts[j+1].oy,sts[j+1].ox});
        
        if(d1 < d2){
          ans.emplace_back(1,sts[j+1].i);
        }else{
          ans.emplace_back(2,ss[ss_tsp[i]].i);
          ans.emplace_back(1,sts[j+1].i);
        }
      }
      ans.emplace_back(2,ss[ss_tsp[i]].i);
    }
    ans.emplace_back(2,ss[ss_tsp[0]].i);
    ans.emplace_back(1,1);

    if(sec > TIME_LIMIT) break;
    ll score = calc_score(ss,ans);
    //cerr << score << endl;
    if(best_score < score){
      best_score = score;
      best_ans = ans;
      best_ss = ss;
    }
  }

  cerr << best_score << endl;
  rep(i,M){
    cout << (int)(best_ss[i].y) << " " << (int)(best_ss[i].x) << endl;
  }
  cout << best_ans.size() << endl;
  rep(i,best_ans.size()){
    cout << best_ans[i].first << " " << best_ans[i].second << endl;
  }
  
  return 0;
}