#955789 (C++23) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	soto800
提出日時	2024-02-25 17:41:58
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	954 ms / 1,000 ms
コード長	7,818 bytes
コンパイル時間	4,705 ms
コンパイル使用メモリ	291,496 KB
実行使用メモリ	6,676 KB
スコア	36,865,876
最終ジャッジ日時	2024-02-25 17:42:54
合計ジャッジ時間	55,236 ms
ジャッジサーバーID （参考情報）	judge10 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	953 ms 6,676 KB
testcase_01	AC	954 ms 6,676 KB
testcase_02	AC	953 ms 6,676 KB
testcase_03	AC	952 ms 6,676 KB
testcase_04	AC	953 ms 6,676 KB
testcase_05	AC	953 ms 6,676 KB
testcase_06	AC	953 ms 6,676 KB
testcase_07	AC	953 ms 6,676 KB
testcase_08	AC	953 ms 6,676 KB
testcase_09	AC	953 ms 6,676 KB
testcase_10	AC	954 ms 6,676 KB
testcase_11	AC	953 ms 6,676 KB
testcase_12	AC	953 ms 6,676 KB
testcase_13	AC	954 ms 6,676 KB
testcase_14	AC	953 ms 6,676 KB
testcase_15	AC	954 ms 6,676 KB
testcase_16	AC	953 ms 6,676 KB
testcase_17	AC	953 ms 6,676 KB
testcase_18	AC	954 ms 6,676 KB
testcase_19	AC	953 ms 6,676 KB
testcase_20	AC	952 ms 6,676 KB
testcase_21	AC	953 ms 6,676 KB
testcase_22	AC	953 ms 6,676 KB
testcase_23	AC	953 ms 6,676 KB
testcase_24	AC	953 ms 6,676 KB
testcase_25	AC	952 ms 6,676 KB
testcase_26	AC	953 ms 6,676 KB
testcase_27	AC	954 ms 6,676 KB
testcase_28	AC	953 ms 6,676 KB
testcase_29	AC	953 ms 6,676 KB
testcase_30	AC	953 ms 6,676 KB
testcase_31	AC	953 ms 6,676 KB
testcase_32	AC	953 ms 6,676 KB
testcase_33	AC	953 ms 6,676 KB
testcase_34	AC	953 ms 6,676 KB
testcase_35	AC	953 ms 6,676 KB
testcase_36	AC	952 ms 6,676 KB
testcase_37	AC	953 ms 6,676 KB
testcase_38	AC	953 ms 6,676 KB
testcase_39	AC	953 ms 6,676 KB
testcase_40	AC	953 ms 6,676 KB
testcase_41	AC	953 ms 6,676 KB
testcase_42	AC	953 ms 6,676 KB
testcase_43	AC	953 ms 6,676 KB
testcase_44	AC	953 ms 6,676 KB
testcase_45	AC	953 ms 6,676 KB
testcase_46	AC	952 ms 6,676 KB
testcase_47	AC	953 ms 6,676 KB
testcase_48	AC	953 ms 6,676 KB
testcase_49	AC	953 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("O3,O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define REP(i, s, n) for (lli i = s; i < n; i++)
#define INF (1LL << 62)
#define mp(a, b) make_pair(a, b)
#define SORT(V) sort(V.begin(), V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) #VariableName
#define LOG1(x)                                                                \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << endl;
#define LOG2(x, y)                                                             \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
         << endl;
#define LOG3(x, y, z)                                                          \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
         << " " << TO_STRING(z) << "=" << z << endl;
#define LOG4(w, x, y, z)                                                       \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << endl;
#define LOG5(w, x, y, z, a)                                                    \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << " " << TO_STRING(a) << "=" << a << endl;
#define LOG6(w, x, y, z, a, b)                                                 \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << " " << TO_STRING(a) << "=" << a << " " << TO_STRING(b) << "=" << b \
         << endl;

#define overload6(a, b, c, d, e, f, g, ...) g
#define LOG(...)                                                               \
  overload6(__VA_ARGS__, LOG6, LOG5, LOG4, LOG3, LOG2, LOG1)(__VA_ARGS__)

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

uint64_t rand64() {
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 7);
  return x = x ^ (x >> 9);
}

double rand_p() { return rand64() * (1.0 / UINT64_MAX); }

#define LOCAL
#define DEBUG 0

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

std::chrono::system_clock::time_point start, endTime;
class Solver {
private:
  lli N;
  vector<pair<lli, lli>> v;
  vector<pair<lli, lli>> baseV;
  mt19937 engine;

  lli calcScore(lli a, lli b) {
    lli v1 = abs(500000000000000000LL - a);
    lli v2 = abs(500000000000000000LL - b);
    return (2000000 - 100000 * log10(max(v1, v2) + 1));
  }

  vector<pair<lli, lli>> createCards(const vector<pair<int, int>> &ans,
                                     const vector<pair<lli, lli>> &baseV) {

    auto v = baseV;
    REP(i, 0, ans.size()) {
      lli a = ans[i].first;
      lli b = ans[i].second;
      lli firstAve = (v[a].first + v[b].first) / 2;
      lli secondAve = (v[a].second + v[b].second) / 2;

      v[a].first = firstAve;
      v[b].first = firstAve;
      v[a].second = secondAve;
      v[b].second = secondAve;
    }
    return move(v);
  }

  lli calcRealScore(const vector<pair<int, int>> &ans,
                    const vector<pair<lli, lli>> &baseV) {
    auto v = createCards(ans, baseV);
    return calcScore(v[0].first, v[0].second);
  }

  lli calcScore(const vector<pair<int, int>> &ans,
                const vector<pair<lli, lli>> &baseV) {
    // auto v = createCards(ans, baseV);
    // lli allScore = 0;
    // for (lli i = 0; i < 3; i++) {
    //   allScore += (10 - i * 3) * calcScore(v[i].first, v[i].second);
    // }
    // return allScore;
    return calcRealScore(ans, baseV);
  }

public:
  Solver() {

    cin >> N;
    v.resize(N);

    REP(i, 0, N) { cin >> v[i].first >> v[i].second; }
    baseV = v;

    engine = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    vector<pair<int, int>> ans;
    const int opeCount = 50;
    int loopCount = 0;
    // 50回答えを出すまでやる
    while (ans.size() < opeCount) {
      //無限ループ防止
      if (loopCount > 500) {
        break;
      }
      int a = 0;
      int b = engine() % N;
      while (a == b) {
        b = engine() % N;
      }
      //カードに次書く数字平均とスコアを計算する。
      lli firstAve = (v[a].first + v[b].first) / 2;
      lli secondAve = (v[a].second + v[b].second) / 2;

      lli nowScore = calcScore(v[0].first, v[0].second);
      lli nextScore = calcScore(firstAve, secondAve);
      LOG(nowScore, nextScore);
      //今のスコアのほうが高ければやり直し
      if (nowScore > nextScore) {
        loopCount++;
        continue;
      }
      //カードの更新
      v[a].first = firstAve;
      v[a].second = secondAve;
      v[b].first = firstAve;
      v[b].second = secondAve;
      ans.push_back(mp(a, b));
      loopCount = 0;
    }

    //初期解ができたら、それを元にして、ランダムに変更していく
    lli nowScore = calcScore(ans, baseV);
    lli nowLoopCount = 0;

    lli bestScore = nowScore;
    vector<pair<int, int>> bestAns = ans;
    while (true) {
      nowLoopCount++;

      endTime = std::chrono::system_clock::now();
      double elapsed =
          std::chrono::duration_cast<std::chrono::milliseconds>(endTime - start)
              .count();

      const double finishElapsedMilisec = 950;
      if (elapsed > finishElapsedMilisec) {
        break;
      }

      static const long double start_temp = 1e2;
      static const long double end_temp = 1e0;
      long double temperature =
          exp(log(start_temp) -
              ((log(start_temp) - log(end_temp)) *
               ((elapsed / 1000.0) * (1.0 / (finishElapsedMilisec / 1000.0)))));

      //変更する答えの箇所を1つ選ぶ
      int a = engine() % opeCount;

      //変更する箇所にて、カード2つを適当に選択する
      int b = engine() % N;
      int c = engine() % N;
      while (b == c) {
        c = engine() % N;
      }
      int preFirst = ans[a].first;
      int preSecond = ans[a].second;
      ans[a].first = b;
      ans[a].second = c;

      lli nextScore = calcScore(ans, baseV);
      lli diffScore = nextScore - nowScore;
      long double prob = std::exp(diffScore / temperature);
      LOG(prob, nowScore, nextScore);
      if (diffScore >= 0 || prob > rand_p()) {
        // if (diffScore >= 0) {
        nowScore = nextScore;
        v = baseV;
      } else {
        ans[a].first = preFirst;
        ans[a].second = preSecond;
      }
      if (bestScore < nextScore) {
        bestScore = nextScore;
        bestAns = ans;
      }
    }
    cerr << "loopCount = " << nowLoopCount << endl;
    cerr << "ansScore = " << calcRealScore(ans, baseV) << endl;

    cout << bestAns.size() << endl;
    for (auto e : bestAns) {
      cout << e.first + 1 << " " << e.second + 1 << endl;
    }
  }
};

int main() {

  start = std::chrono::system_clock::now();

  //まずは適当に50個選ぶ
  Solver solver;

  return 0;
}

yukicoder

結果

テストケース

ソースコード