結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー BinomialSheep
提出日時 2022-08-01 12:14:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 806 ms / 1,000 ms
コード長 8,311 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,221 ms
実行使用メモリ 4,828 KB
スコア 6,929,972
最終ジャッジ日時 2022-08-01 12:15:00
合計ジャッジ時間 29,071 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: ラムダ関数内:
main.cpp:156:38: 警告: ‘idx2’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  156 |           value.emplace_back(2, idx2 + 1);
      |                                 ~~~~~^~~
main.cpp:155:38: 警告: ‘idx1’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  155 |           value.emplace_back(2, idx1 + 1);
      |                                 ~~~~~^~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// デバッグ用マクロ：https://naskya.net/post/0002/
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
using namespace std;
using namespace chrono;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvi = vector<vector<vector<int>>>;
using pii = pair<int, int>;
// #include <atcoder/all>
// using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
// #define MAX 10000
#define INFTY (1 << 30)
// 浮動小数点の誤差を考慮した等式
#define EPS (1e-10)
#define equal(a, b) (fabs((a) - (b)) < EPS)

template <typename T>
inline bool chmax(T &a, T b) {
  return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
  return ((a > b) ? (a = b, true) : (false));
}

// 焼きなまし法の参考にしたページ
// https://shindannin.hatenadiary.com/entry/2021/03/06/115415

// 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift
// https://ja.wikipedia.org/wiki/Xorshift
static uint32_t randXor() {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;

  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

// 0以上1未満の小数をとる乱数
static double rand01() { return (randXor() + 0.5) * (1.0 / UINT_MAX); }

struct Solver {
  int N, M;
  vi a, b;
  // α
  int A = 5;

  vpii stupidInit() {
    vpii ret;
    rep(i, N) ret.emplace_back(1, i + 1);
    ret.emplace_back(1, 1);
    return ret;
  }

  // 惑星を経由しない
  vpii greedyInit() {
    vpii ret;
    vector<vpii> distList(N);

    auto dist = [](int x1, int y1, int x2, int y2) {
      return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    };

    rep(i, N) rep(j, i) {
      int x1 = a[i];
      int y1 = b[i];
      int x2 = a[j];
      int y2 = b[j];
      auto d = A * A * dist(x1, y1, x2, y2);
      distList[i].emplace_back(d, j);
      distList[j].emplace_back(d, i);
    }
    rep(i, N) sort(all(distList[i]));

    vi color(N);
    int now = 0;
    color[0] = 1;
    ret.emplace_back(1, 1);
    rep(i, N) {
      for (auto p : distList[now]) {
        if (color[p.second]) continue;
        now = p.second;
        color[p.second] = 1;
        ret.emplace_back(1, now + 1);
        break;
      }
    }
    ret.emplace_back(1, 1);
    return ret;
  }

  // 惑星を経由する
  vpii greedyInit2(vpii &cd) {
    vpii ret;
    vector<vpii> distList(N);
    map<pii, vpii> mp;

    auto dist = [&](int x1, int y1, int x2, int y2, int xi, int yi) {
      vpii value;

      ll dt = A * A * (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
      rep(i, (int)cd.size()) {
        auto x = cd[i].first;
        auto y = cd[i].second;
        ll tmp = A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y));
        tmp += A * (ll)((x - x2) * (x - x2) + (y - y2) * (y - y2));
        if (chmin(dt, tmp)) {
          value.clear();
          value.emplace_back(2, i + 1);
        }
      }
      ll tmp1 = INFTY;
      ll tmp2 = INFTY;
      int idx1, idx2;
      rep(i, (int)cd.size()) {
        auto x = cd[i].first;
        auto y = cd[i].second;
        if (chmin(tmp1, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))))
          idx1 = i;
        if (chmin(tmp2, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))))
          idx2 = i;
      }
      if (idx1 != idx2) {
        auto xx1 = cd[idx1].first;
        auto yy1 = cd[idx1].first;
        auto xx2 = cd[idx2].first;
        auto yy2 = cd[idx2].first;
        ll tmp3 = (ll)((xx1 - xx2) * (xx1 - xx2) + (yy1 - yy2) * (yy1 - yy2));
        if (chmin(dt, tmp1 + tmp2 + tmp3)) {
          value.clear();
          value.emplace_back(2, idx1 + 1);
          value.emplace_back(2, idx2 + 1);
        }
      }
      mp[make_pair(xi, yi)] = value;
      return dt;
    };

    rep(i, N) rep(j, i) {
      int x1 = a[i];
      int y1 = b[i];
      int x2 = a[j];
      int y2 = b[j];
      auto d = A * A * dist(x1, y1, x2, y2, i, j);
      mp[make_pair(j, i)] = mp[make_pair(i, j)];
      distList[i].emplace_back(d, j);
      distList[j].emplace_back(d, i);
    }
    rep(i, N) sort(all(distList[i]));

    vi color(N);
    int now = 0;
    color[0] = 1;
    ret.emplace_back(1, 1);
    rep(i, N) {
      for (auto p : distList[now]) {
        if (color[p.second]) continue;
        for (auto pp : mp[make_pair(now, p.second)]) {
          ret.push_back(pp);
        }
        ret.emplace_back(1, p.second + 1);
        now = p.second;
        color[p.second] = 1;
        break;
      }
    }
    ret.emplace_back(1, 1);
    return ret;
  }

  // 宇宙ステーションの初期配置
  vpii initStation() {
    vpii ret;
    ret.emplace_back(800, 500);
    ret.emplace_back(200, 500);
    ret.emplace_back(500, 800);
    ret.emplace_back(500, 200);
    ret.emplace_back(600, 600);
    ret.emplace_back(600, 400);
    ret.emplace_back(400, 600);
    ret.emplace_back(400, 400);
    return ret;
  }

  // シンプルなスコア計算
  ll calcScore(vpii &tr) {
    ll ret = 0;
    int len = (int)tr.size();

    auto dist = [](int x1, int y1, int x2, int y2) {
      return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    };

    rep(i, len - 1) {
      if (tr[i].first == 1 && tr[i + 1].first == 1) {
        int x1 = a[tr[i].second - 1];
        int y1 = b[tr[i].second - 1];
        int x2 = a[tr[i + 1].second - 1];
        int y2 = b[tr[i + 1].second - 1];
        ret += A * A * dist(x1, y1, x2, y2);
      } else if (tr[i].first == 2 && tr[i + 1].first == 2) {
        // TODO
      } else {
        // TODO
      }
    }
    return ret;
  }

  void solve() {
    /* 時間計測 */
    auto startClock = system_clock::now();
    /* input */
    cin >> N >> M;
    a.resize(N);
    b.resize(N);
    rep(i, N) cin >> a[i] >> b[i];

    /* solve */
    // 初期設定
    vpii cd = initStation();
    // vpii tr = stupidInit();
    // vpii tr = greedyInit();
    vpii tr = greedyInit2(cd);

    // debug(calcScore(tr));
    auto maxScore = calcScore(tr);

    /* 焼きなまし法 */
    const static double START_TEMP = 1500;  // 開始時の温度
    const static double END_TEMP = 100;     // 終了時の温度
    const static double END_TIME = 0.8;     // 終了時間（秒）
    double time = 0.0;                      // 経過時間（秒）

    // ループ回数のデバッグ用
    ll cnt = 0;
    // 答え用
    do {
      cnt++;
      // 進捗。開始時が0.0で、終了時が1.0
      const double progressRatio = time / END_TIME;
      const double temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;

      // 初挑戦
      // バックアップ
      vpii oldCd = cd;
      // ランダム変更
      int d = randXor() % 8;
      int dx = randXor() % 100;
      int dy = randXor() % 100;
      cd[d].first = (cd[d].first + dx) % 1000;
      cd[d].second = (cd[d].second + dy) % 1000;
      // スコア計算
      vpii nowTr = greedyInit2(cd);
      double nowScore = calcScore(nowTr);
      debug(nowScore, maxScore);
      if (nowScore <= maxScore) {
        maxScore = nowScore;
        tr.clear();
        tr = nowTr;
      } else {
        cd = oldCd;
      }

      // 時間更新
      time =
          ((double)duration_cast<microseconds>(system_clock::now() - startClock)
               .count() *
           1e-6);

    } while (time < END_TIME);

    /* output */
    debug(cnt);
    int V = (int)tr.size();
    assert(tr[0].second == 1);
    assert(tr[V - 1].second == 1);

    rep(i, M) cout << cd[i].first << " " << cd[i].second << "\n";

    cout << V << endl;
    rep(i, V) cout << tr[i].first << " " << tr[i].second << "\n";
  }
};

int main() {
  int ts = 1;
  rep(ti, ts) {
    Solver solver;
    solver.solve();
  }
  return 0;
}
0