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

• 問題: No.5020 Averaging
• ユーザー: siman
• 提出日時: 2024-02-25 13:40:52
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 955 ms / 1,000 ms
• コード長: 4,509 bytes
• コンパイル時間: 1,609 ms
• コンパイル使用メモリ: 145,308 KB
• 実行使用メモリ: 6,676 KB
• スコア: 14,749,563
• 最終ジャッジ日時: 2024-02-25 13:41:44
• 合計ジャッジ時間: 51,991 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

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

ソースコード

#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>
#include <random>
#include <chrono>

using namespace std;
typedef long long ll;

constexpr int N = 45;
constexpr int T = 50;
constexpr double TIME_LIMIT = 0.95;
constexpr ll
BASE_SCORE = 500000000000000000;

ll A[N];
ll B[N];
ll A_copy[N];
ll B_copy[N];

class Xorshift {
public:
  Xorshift(uint64_t seed = 88675123) {
    _x = 123456789;
    _y = 362436069;
    _z = 521288629;
    _w = seed;

    for (int i = 0; i < 100; ++i) {
      next();
    }
  }

  uint64_t next(uint64_t a, uint64_t b) {
    return a + (next() % (b - a + 1));
  }

  uint64_t next() {
    uint64_t t = _x ^ (_x << 11);
    _x = _y;
    _y = _z;
    _z = _w;
    _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
    return _w;
  }

  double random_double() {
    return static_cast<double>(next()) / UINT64_MAX;
  }

  double random_double(double a, double b) {
    return a + (b - a) * random_double();
  }

private:
  uint64_t _x, _y, _z, _w;
};

class Timer {
public:
  Timer() {
    begin();
    _duration = 0.0;
  }

  void begin() {
    _start_at = chrono::system_clock::now();
  }

  double get_time() {
    chrono::system_clock::time_point end_at = chrono::system_clock::now();
    _duration = chrono::duration_cast<std::chrono::nanoseconds>(end_at - _start_at).count();
    return _duration / 1000000000.0;
  }

  double progress(double time_limit) {
    return get_time() / time_limit;
  }

private:
  chrono::system_clock::time_point _start_at;
  double _duration;
};

Xorshift g_rng;

class Solver {
public:
  void run() {
    load_data();
    setup();

    auto res = sa();

    /*
    cout << N << endl;
    for (int i = 0; i < N; ++i) {
      cout << A[i] << " " << B[i] << endl;
    }
     */
    cout << res.size() << endl;
    for (int i = 0; i < T; ++i) {
      cout << res[i].first << " " << res[i].second << endl;
    }
  }

private:
  void load_data() {
    int _N;
    cin >> _N;

    for (int i = 0; i < N; ++i) {
      cin >> A[i] >> B[i];
    }
  }

  void setup() {
  }

  vector <pair<int, int>> sa(double time_limit = TIME_LIMIT) {
    Timer timer;
    int U[T], V[T];
    for (int i = 0; i < T; ++i) {
      int u, v;
      do {
        u = g_rng.next(0, N - 1);
        v = g_rng.next(0, N - 1);
      } while (u == v);

      U[i] = u;
      V[i] = v;
    }

    int best_U[T], best_V[T];
    memcpy(best_U, U, sizeof(U));
    memcpy(best_V, V, sizeof(V));
    int cur_score = calc_score_full(U, V);
    int best_score = cur_score;

    double cur_time = timer.get_time();
    double total_diff = 0.0;
    double t = 0.1;
    ll R = 100000000;
    int try_count = 0;

    while (cur_time < time_limit) {
      cur_time = timer.get_time();
      double remain_time = (time_limit - cur_time) / time_limit;

      int score = calc_score_full(U, V);
      double diff_score = cur_score - score;
      total_diff += fabs(diff_score);

      if (diff_score > 0 || (g_rng.next() % R < R * exp(diff_score / (t * pow(remain_time, 2))))) {
        cur_score = score;

        if (best_score < score) {
          best_score = score;
          memcpy(best_U, U, sizeof(U));
          memcpy(best_V, V, sizeof(V));
        }
      } else {
      }

      ++try_count;
      double average_diff = total_diff / try_count;
      t = 0.25 * remain_time * average_diff;
    }

    fprintf(stderr, "try_count: %d, best_score: %d\n", try_count, best_score);

    vector <pair<int, int>> res;
    for (int i = 0; i < T; ++i) {
      res.emplace_back(make_pair(best_U[i] + 1, best_V[i] + 1));
    }

    return res;
  }

  int calc_score_full(int *U, int *V) {
    memcpy(A_copy, A, sizeof(A));
    memcpy(B_copy, B, sizeof(B));

    for (int i = 0; i < N; ++i) {
      int u = U[i];
      int v = V[i];
      ll sum_a = A_copy[u] + A_copy[v];
      ll sum_b = B_copy[u] + B_copy[v];
      A_copy[u] = sum_a >> 1;
      A_copy[v] = sum_a >> 1;
      B_copy[u] = sum_b >> 1;
      B_copy[v] = sum_b >> 1;
    }

    ll diff_A = abs(BASE_SCORE - A_copy[0]);
    ll diff_B = abs(BASE_SCORE - B_copy[0]);
    ll max_diff = max(diff_A, diff_B);

    // Score = (int)(2000000.0 - 100000.0 * math.log10(1.0 * max(ErrorA, ErrorB) + 1.0))
    int score = (int) (2000000.0 - 100000.0 * log10(1.0 * max_diff + 1.0));

    return score;
  }
};

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  Solver solver;
  solver.run();

  return 0;
}