結果

問題 No.5020 Averaging
ユーザー simansiman
提出日時 2024-02-25 14:00:10
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 4,789 bytes
コンパイル時間 1,668 ms
コンパイル使用メモリ 145,564 KB
実行使用メモリ 6,676 KB
スコア 50,020,203
最終ジャッジ日時 2024-02-25 14:01:03
合計ジャッジ時間 52,627 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 952 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 952 ms
6,676 KB
testcase_06 AC 951 ms
6,676 KB
testcase_07 AC 952 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 952 ms
6,676 KB
testcase_14 AC 952 ms
6,676 KB
testcase_15 AC 952 ms
6,676 KB
testcase_16 AC 951 ms
6,676 KB
testcase_17 AC 952 ms
6,676 KB
testcase_18 AC 952 ms
6,676 KB
testcase_19 AC 952 ms
6,676 KB
testcase_20 AC 952 ms
6,676 KB
testcase_21 AC 952 ms
6,676 KB
testcase_22 AC 952 ms
6,676 KB
testcase_23 AC 952 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 952 ms
6,676 KB
testcase_29 AC 952 ms
6,676 KB
testcase_30 AC 951 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 951 ms
6,676 KB
testcase_37 AC 952 ms
6,676 KB
testcase_38 AC 952 ms
6,676 KB
testcase_39 AC 952 ms
6,676 KB
testcase_40 AC 953 ms
6,676 KB
testcase_41 AC 951 ms
6,676 KB
testcase_42 AC 952 ms
6,676 KB
testcase_43 AC 952 ms
6,676 KB
testcase_44 AC 952 ms
6,676 KB
testcase_45 AC 952 ms
6,676 KB
testcase_46 AC 951 ms
6,676 KB
testcase_47 AC 952 ms
6,676 KB
testcase_48 AC 952 ms
6,676 KB
testcase_49 AC 952 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 idx = g_rng.next(0, T - 1);
      int u, v;
      do {
        u = 0;
        v = g_rng.next(0, N - 1);
      } while (u == v);

      int back_u = U[idx];
      int back_v = V[idx];
      U[idx] = u;
      V[idx] = v;

      int score = calc_score_full(U, V);
      double diff_score = score - cur_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 {
        U[idx] = back_u;
        V[idx] = back_v;
      }

      ++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 < T; ++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;
}
0