#783412 (C++17) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: kens
• 提出日時: 2022-07-30 17:57:47
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 983 ms / 1,000 ms
• コード長: 5,962 bytes
• コンパイル時間: 4,436 ms
• 実行使用メモリ: 5,160 KB
• スコア: 8,892,100
• 最終ジャッジ日時: 2022-07-30 17:58:43
• 合計ジャッジ時間: 36,844 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
using P = pair<ll,ll>;
constexpr int N = 100;
constexpr int M = 8;
constexpr ll A = 5;
constexpr int time_limit = 980;
constexpr ll INF = 1e9;

// simulated annealing
constexpr double temp_start = 10.0;
constexpr double temp_end = 0.00001; 
constexpr int climb_loop = 1e7;

ll a[N], b[N];

// random
int seed = 12345;
mt19937 eng(seed);
uniform_real_distribution<> uniform_01;

// timer
class Timer {
private:
  chrono::system_clock::time_point start;
public:
  Timer() {
    start = chrono::system_clock::now();
  }

  int get_ms() {
    auto end = chrono::system_clock::now();
    auto t = chrono::duration_cast<chrono::milliseconds>(end-start).count();
    return t;
  }
};

vector<P> clustering() {
  vector<P> point;
  rep(i,N) point.push_back(P(a[i],b[i]));
  while(point.size() > M) {
    int psz = point.size();
    ll dm = INF; int p1 = -1, p2 = -1;
    rep(i,psz) for(int j = i+1; j < psz; j++) {
      ll dx = point[i].first-point[j].first; 
      ll dy = point[i].second-point[j].second; 
      ll dist = dx*dx + dy*dy;
      if(dist < dm) {
        dm = dist;
        p1 = i;
        p2 = j;
      }
    }
    vector<P> point_new;
    rep(i,psz) if(i != p1 and i != p2) point_new.push_back(point[i]);
    point_new.push_back(P((point[p1].first+point[p2].first)/2,(point[p1].second+point[p2].second)/2));
    swap(point,point_new);
  }
  return point;
}

void solve() {
  Timer timer;

  // input
  int hello;
  cin >> hello >> hello;
  rep(i,N) cin >> a[i] >> b[i];

  vector<vector<ll>> dpp(N,vector<ll>(N));
  rep(i,N) rep(j,N) {
    ll dx = a[i]-a[j], dy = b[i]-b[j];
    dpp[i][j] = dx*dx + dy*dy;
  }

  // clustering
  vector<P> pg = clustering();

  vector<vector<ll>> dpm(N,vector<ll>(M));
  rep(i,N) rep(j,M) {
    ll dx = a[i]-pg[j].first, dy = b[i]-pg[j].second;
    dpm[i][j] = dx*dx + dy*dy;
  }

  vector<vector<ll>> dmm(M,vector<ll>(M));
  rep(i,M) rep(j,M) {
    ll dx = pg[i].first-pg[j].first, dy = pg[i].second-pg[j].second;
    dmm[i][j] = dx*dx + dy*dy;
  }

  vector<int> seq(N+1);
  rep(i,N) seq[i] = i;
  seq[N] = 0;

  ll score = 0;
  for(int u = 1; u <= N; u++) score += dpp[seq[u]][seq[u-1]]*A*A;

  // best sequence
  ll best_score = score;
  vector<int> best_seq = seq;

  auto calc_dist = [&](int u, int v) -> ll {
    ll res = dpp[u][v]*A*A;

    // via one station
    rep(j,M) {
      ll d1 = dpm[u][j]*A + dpm[v][j]*A;
      if(d1 < res) res = d1;
    }
    // vis two station 
    rep(j,M) rep(k,M) {
      ll d2 = dpm[u][j]*A + dmm[j][k] + dpm[v][k]*A;
      if(d2 < res) res = d2;
    }

    return res;
  };


  constexpr int SIGMA = 50;
  constexpr int PROP = 20;
  normal_distribution<> nd(0,SIGMA);

  auto update_dpm = [&](int s) {
    rep(i,N) {
      ll dx = a[i]-pg[s].first, dy = b[i]-pg[s].second;
      dpm[i][s] = dx*dx + dy*dy;
    }
  };

  auto update_dmm = [&](int s) {
    rep(i,M) {
      ll dx = pg[i].first-pg[s].first, dy = pg[i].second-pg[s].second;
      dmm[i][s] = dx*dx + dy*dy;
      dmm[s][i] = dx*dx + dy*dy;
    }
  };

  int last = 0;

  // two opt with clustering + move cluster point
  rep(cn,climb_loop) {
    if(timer.get_ms() > time_limit) break;
    double temp = temp_start + (temp_end - temp_start)*cn/climb_loop;

    int id = eng() % PROP;

    if(id) {
      // 経路変更
      int s = eng() % (N-1) + 1;
      int t = eng() % (N-1) + 1;

      if(s == t) continue;
      if(s > t) swap(s,t);

      ll score_diff = calc_dist(seq[t],seq[s-1]) + calc_dist(seq[s],seq[t+1]) - calc_dist(seq[s],seq[s-1]) - calc_dist(seq[t],seq[t+1]);
      if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
        score += score_diff;
        reverse(seq.begin()+s,seq.begin()+t+1);
      }
    } else {
      // 位置変更
      int dx = nd(eng);
      int dy = nd(eng);
      if(dx == 0 and dy == 0) continue;
      int s = eng() % M;

      pg[s].first += dx; pg[s].second += dy;
      update_dpm(s);
      update_dmm(s);

      ll score_new = 0;
      for(int i = 1; i <= N; i++) score_new += calc_dist(seq[i-1],seq[i]);
      ll score_diff = score_new - score;

      if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
        score += score_diff;
      } else {
        pg[s].first -= dx; pg[s].second -= dy;
        update_dpm(s);
        update_dmm(s);
      }
    }

    if(score < best_score) {
      last = timer.get_ms();
      best_score = score;
      best_seq = seq;
    }
  }

  // 復元
  ll score_cluster = 0;
  vector<P> seq_cluster;

  seq_cluster.push_back(P(1,0));

  // consider clustering
  for(int i = 1; i <= N; i++) {
    ll res = dpp[best_seq[i]][best_seq[i-1]]*A*A;
    ll s1 = -1, s2 = -1;

    // via one station
    rep(j,M) {
      ll d1 = dpm[best_seq[i-1]][j]*A + dpm[best_seq[i]][j]*A;
      if(d1 < res) {
        res = d1;
        s1 = j;
      }
    }
    // vis two station 
    rep(j,M) rep(k,M) {
      ll d2 = dpm[best_seq[i-1]][j]*A + dmm[j][k] + dpm[best_seq[i]][k]*A;
      if(d2 < res) {
        res = d2;
        s1 = j; s2 = k;
      }
    }

    score_cluster += res;
    if(s1 == -1 and s2 == -1) {
      seq_cluster.push_back(P(1,best_seq[i]));
    } else if(s1 != -1 and s2 == -1) {
      seq_cluster.push_back(P(2,s1));
      seq_cluster.push_back(P(1,best_seq[i]));
    } else {
      seq_cluster.push_back(P(2,s1));
      seq_cluster.push_back(P(2,s2));
      seq_cluster.push_back(P(1,best_seq[i]));
    }
  }


  int final_score = round(1e9/(1000.0+sqrt((double)score_cluster)));  

  // cerr << best_score << endl;
  
  cerr << "Time " << timer.get_ms() << endl;
  cerr << "Score = " << final_score << endl;

  rep(i,M) cout << pg[i].first << " " << pg[i].second << endl;
  cout << seq_cluster.size() << endl;
  for(auto [t, v] : seq_cluster) cout << t << " " << v+1 << endl;
}

int main() {
  solve();
  return 0;
}