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

提出ソース

結果

問題	No.5020 Averaging
ユーザー	neterukun
提出日時	2024-02-25 16:43:01
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	954 ms / 1,000 ms
コード長	6,287 bytes
コンパイル時間	2,171 ms
コンパイル使用メモリ	179,728 KB
実行使用メモリ	6,676 KB
スコア	41,148,794
最終ジャッジ日時	2024-02-25 16:45:59
合計ジャッジ時間	52,768 ms
ジャッジサーバーID （参考情報）	judge15 / judge10
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	953 ms 6,676 KB
testcase_01	AC	952 ms 6,676 KB
testcase_02	AC	952 ms 6,676 KB
testcase_03	AC	953 ms 6,676 KB
testcase_04	AC	953 ms 6,676 KB
testcase_05	AC	952 ms 6,676 KB
testcase_06	AC	952 ms 6,676 KB
testcase_07	AC	952 ms 6,676 KB
testcase_08	AC	952 ms 6,676 KB
testcase_09	AC	953 ms 6,676 KB
testcase_10	AC	951 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	952 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	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	951 ms 6,676 KB
testcase_36	AC	953 ms 6,676 KB
testcase_37	AC	953 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	953 ms 6,676 KB
testcase_42	AC	952 ms 6,676 KB
testcase_43	AC	954 ms 6,676 KB
testcase_44	AC	952 ms 6,676 KB
testcase_45	AC	953 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	952 ms 6,676 KB

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

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))

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

using namespace std::chrono;
using namespace std;
struct Timer {
    system_clock::time_point start;

    Timer() { reset(); }

    void reset() { start = system_clock::now(); }

    double sec_elapsed() const {
        return duration_cast<milliseconds>(system_clock::now() - start).count() / 1000.0;
    }
};

constexpr int N = 45;
constexpr int M = 50;
long long A[N];
long long B[N];

void input() {
    int tmp;
    std::cin >> tmp;
    REP(i, N) {
        std::cin >> A[i] >> B[i];
    }
}

struct State {
    std::vector<std::pair<int, int>> operations;
    std::vector<long long> testA;
    std::vector<long long> testB;
    double rand;
        
    int old_index, old_i, old_j;
    int old_index0, old_index1, old_pattern, old_i0, old_j0, old_i1, old_j1;
    State() {
        REP(k, M) {
            int i = rand64() % N;
            int j = rand64() % N;
            operations.emplace_back(i, j);
        }
        testA.resize(N);
        testB.resize(N);
    }

    void modify() {
        rand = rand_p();
        if (rand < 0.2) {
            int index = rand64() % M;
            int i = rand64() % (N + 25);
            int j = rand64() % (N + 25);
            if (i >= N) i = 0;
            if (j >= N) j = 0;
            old_index = index;
            old_i = operations[index].first;
            old_j = operations[index].second;
            operations[index] = std::make_pair(i, j);
        } else {
            int index0 = rand64() % M;
            int index1 = rand64() % M;
            old_pattern = rand64() % 4;
            old_index0 = index0;
            old_index1 = index1;
            if (old_pattern == 0)
                std::swap(operations[index0].first, operations[index1].first);
            else if (old_pattern == 1)
                std::swap(operations[index0].first, operations[index1].second);
            else if (old_pattern == 2)
                std::swap(operations[index0].second, operations[index1].first);
            else if (old_pattern == 3)
                std::swap(operations[index0].second, operations[index1].second);
        }
    }

    void rollback() {
        if (rand < 0.2) {
            operations[old_index] = std::make_pair(old_i, old_j);
        } else {
            if (old_pattern == 0)
                std::swap(operations[old_index0].first, operations[old_index1].first);
            else if (old_pattern == 1)
                std::swap(operations[old_index0].first, operations[old_index1].second);
            else if (old_pattern == 2)
                std::swap(operations[old_index0].second, operations[old_index1].first);
            else if (old_pattern == 3)
                std::swap(operations[old_index0].second, operations[old_index1].second);
        }
    }

    long long calc_score() {
        REP(i, N) {
            testA[i] = A[i];
            testB[i] = B[i];
        }

        for (auto &op : operations) {
            int i = op.first;
            int j = op.second;
            long long avgA = (testA[i] + testA[j]) / 2LL;
            long long avgB = (testB[i] + testB[j]) / 2LL;
            testA[i] = avgA;
            testA[j] = avgA;
            testB[i] = avgB;
            testB[j] = avgB;
        }

        long long ErrorA = abs(500000000000000000LL - testA[0]);
        long long ErrorB = abs(500000000000000000LL - testB[0]);
        long long Score = (long long)(2000000.0L - 100000.0L * log10(1.0L * max(ErrorA, ErrorB) + 1.0L));
        // long long Score = -max(ErrorA, ErrorB);
        return Score;
    }
    
    void print() {
        int invalid_count = 0;
        REP(i, M) {
            int a = operations[i].first;
            int b = operations[i].second;
            if (a == b) {
                invalid_count += 1;
            }
        }
        std::cout << M - invalid_count << std::endl;
        REP(i, M) {
            int a = operations[i].first;
            int b = operations[i].second;
            if (a != b) {
                std::cout << a + 1<< " " << b + 1 << std::endl;
            }
        }
    }
};


State annealing(State cur_state, const Timer &timer, const double time_limit) {
    // 温度設定
    const double start_temp = 1e4;
    const double end_temp = 1e0;

    double inv_temp = 1.0 / start_temp;

    int iter_count = 0;
    long long cur_score = cur_state.calc_score();

    State best_state = cur_state;
    long long best_score = best_state.calc_score();
    
    double start_time = timer.sec_elapsed();
    double now = start_time;

    while (now < time_limit) {
      
        if (iter_count & 1024) {
            now = timer.sec_elapsed();
            const double time_ratio = (now - start_time) / (time_limit - start_time);
            // const double temp = start_temp + (end_temp - start_temp) * time_ratio;  // 線形
            const double temp = start_temp * std::pow(end_temp / start_temp, time_ratio);  // pow 	
            inv_temp = 1.0 / temp;
        }

        cur_state.modify();
        long long new_score = cur_state.calc_score();

        double prob = std::exp((new_score - cur_score) * inv_temp);

        if (prob > rand_p()) {
            cur_score = new_score;
        } else {
            cur_state.rollback();
        }
        if (cur_score > best_score) {
            best_score = cur_score;
            best_state = cur_state;
        }
        iter_count += 1;
    }
    std::cerr << iter_count << std::endl;
    return best_state;
}


int main() {
    input();
    Timer timer;

    State state;

    state = annealing(state, timer, 0.95);

    std::cerr << state.calc_score() << std::endl;
    state.print();
}

yukicoder

結果

テストケース

ソースコード