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

• 問題: No.5007 Steiner Space Travel
• ユーザー: kens
• 提出日時: 2022-07-30 15:34:11
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 108 ms / 1,000 ms
• コード長: 2,275 bytes
• コンパイル時間: 3,963 ms
• 実行使用メモリ: 4,104 KB
• スコア: 6,098,586
• 最終ジャッジ日時: 2022-07-30 15:34:20
• 合計ジャッジ時間: 8,069 ms
• ジャッジサーバーID （参考情報）: judge10 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	101 ms; 3,700 KB
testcase_01	AC	98 ms; 3,864 KB
testcase_02	AC	93 ms; 3,620 KB
testcase_03	AC	106 ms; 3,816 KB
testcase_04	AC	106 ms; 4,104 KB
testcase_05	AC	97 ms; 3,676 KB
testcase_06	AC	95 ms; 3,748 KB
testcase_07	AC	96 ms; 3,748 KB
testcase_08	AC	98 ms; 3,704 KB
testcase_09	AC	99 ms; 3,800 KB
testcase_10	AC	95 ms; 3,700 KB
testcase_11	AC	94 ms; 3,944 KB
testcase_12	AC	98 ms; 3,596 KB
testcase_13	AC	95 ms; 3,920 KB
testcase_14	AC	95 ms; 3,916 KB
testcase_15	AC	100 ms; 3,848 KB
testcase_16	AC	107 ms; 3,664 KB
testcase_17	AC	96 ms; 3,732 KB
testcase_18	AC	96 ms; 3,920 KB
testcase_19	AC	97 ms; 3,928 KB
testcase_20	AC	97 ms; 3,588 KB
testcase_21	AC	97 ms; 3,976 KB
testcase_22	AC	108 ms; 3,912 KB
testcase_23	AC	104 ms; 3,956 KB
testcase_24	AC	96 ms; 3,676 KB
testcase_25	AC	97 ms; 3,896 KB
testcase_26	AC	94 ms; 3,840 KB
testcase_27	AC	104 ms; 3,828 KB
testcase_28	AC	108 ms; 3,904 KB
testcase_29	AC	95 ms; 3,660 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 = 900;

// simulated annealing
constexpr double temp_start = 1.0;
constexpr double temp_end = 0.00001; 
constexpr int climb_loop = 1000000;

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;
  }
};

inline ll dist2(int u, int v, ll alpha) {
  ll dx = a[u]-a[v], dy = b[u]-b[v];
  return alpha*(dx*dx + dy*dy);
}

void solve() {
  Timer timer;

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

  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 += dist2(seq[u],seq[u-1],A*A);

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

  // two opt
  rep(cn,climb_loop) {
    if(timer.get_ms() > time_limit) break;
    double temp = temp_start + (temp_end - temp_start)*cn/climb_loop;
    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 = dist2(seq[t],seq[s-1],A*A) + dist2(seq[s],seq[t+1],A*A) - dist2(seq[s],seq[s-1],A*A) - dist2(seq[t],seq[t+1],A*A);
    if(score_diff < 0 || uniform_01(eng) < exp((double)-score_diff/temp)) {
      score += score_diff;
      reverse(seq.begin()+s,seq.begin()+t+1);

      if(score < best_score) {
        best_score = score;
        best_seq = seq;
      }
    }
  }

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

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

  rep(i,M) cout << 0 << " " << 0 << endl;
  cout << N+1 << endl;
  rep(i,N+1) cout << 1 << " " << best_seq[i]+1 << endl;
}

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