結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー tabae326
提出日時 2025-02-25 21:35:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,803 ms / 2,000 ms
コード長 5,909 bytes
コンパイル時間 1,539 ms
コンパイル使用メモリ 116,152 KB
実行使用メモリ 6,824 KB
スコア 47,757,591
最終ジャッジ日時 2025-02-25 21:37:19
合計ジャッジ時間 95,946 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef __COMMON_HPP__
#define __COMMON_HPP__

#include <iostream>
#include <vector>
#include <cmath>
#include <atcoder/modint>
using namespace std;
using ll = long long;
using mint = atcoder::static_modint<100000000>;

namespace common {
    int n;
    vector<vector<mint>> a;
    void read();
    void update(vector<vector<mint>>&);
    inline int diff(const mint, const mint);
    inline ll calc_score(const vector<vector<mint>>&);
};

void common::read() {
    cin >> n;
    a.resize(n, vector<mint>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            int tmp;
            cin >> tmp;
            a[i][j] = tmp;
        }
    }
}

void common::update(vector<vector<mint>> &b) {
    for(int i = n-1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            b[i-1][j] = b[i][j] + b[i][j+1];
        }
    }
}

inline int common::diff(const mint x, const mint y) {
    int d = (x-y).val();
    return min(d, 100000000-d);
}

inline ll common::calc_score(const vector<vector<mint>> &b) {
    ll score = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            score = max<ll>(score, diff(a[i][j], b[i][j]));
        }
    }
    return 50000000-score;
}

#endif
#ifndef __STATE_HPP__
#define __STATE_HPP__

#ifndef __RYUKA_HPP__
#define __RYUKA_HPP__

#include <random>
using namespace std;

struct RandGenerator {

    random_device seed_gen;
    mt19937 engine;
    mt19937_64 engine64;
    static const int pshift = 1000000000;
    
    RandGenerator() : engine(seed_gen()), engine64(seed_gen()) {}
    
    int rand(int mod) {
        return engine() % mod;
    }
    
    long long randll(long long mod) {
        return engine64() % mod;
    } 
    
    bool pjudge(double p) {
        int p_int;
        if(p > 1) p_int = pshift;
        else p_int = p * pshift;
        return rand(pshift) < p_int;
    }

} ryuka;

#endif
#include <numeric>
#include <algorithm>
#include <cassert>

using namespace std;
using namespace common;

extern RandGenerator ryuka;

struct State {
    static constexpr long long inf = 1LL<<60;
    long long score;
    vector<vector<mint>> b;
    State() : score(-inf) {};
    long long calc_score();
    void print();
    static State initState();
    static State generateState(const State& input_state);
};

long long State::calc_score() {
    score = common::calc_score(b);
    return score;
}

void State::print() {
    for(int i = 0; i < n; i++) {
        cout << b[n-1][i].val() << (i == n-1 ? '\n' : ' ');
    }
}

State State::initState() {
    State res;
    res.b = a;
    update(res.b);
    res.calc_score();
    return res;
}

State State::generateState(const State& input_state) {
    State res = input_state;
    int i = ryuka.rand(n);
    int v = ryuka.rand(100000000);
    res.b[n-1][i] = v;
    update(res.b);
    res.calc_score();
    return res;
}

#endif
#ifndef __ANNEALER_HPP__
#define __ANNEALER_HPP__

#ifndef __TOKI_HPP__
#define __TOKI_HPP__

#include <sys/time.h>
#include <cstddef>

struct Timer {

    double global_start;
    
    double gettime() {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }
    
    void init() {
        global_start = gettime();
    }
    
    double elapsed() {
        return gettime() - global_start;
    }
} toki;

#endif

extern Timer toki;
extern RandGenerator ryuka;

template<class STATE>
struct IterationControl {
    long long iteration_counter;
    long long swap_counter;
    double average_time;
    double start_time;
    IterationControl() : iteration_counter(0), swap_counter(0) {}
    STATE climb(double time_limit, STATE initial_state);
    STATE anneal(double time_limit, double temp_start, double temp_end, STATE initial_state);
};

template<class STATE>
STATE IterationControl<STATE>::climb(double time_limit, STATE initial_state) {
    start_time = toki.gettime();
    average_time = 0;
    STATE best_state = initial_state;
    double time_stamp = start_time;
    cerr << "Starts climbing...\n";
    while(time_stamp - start_time + average_time < time_limit) {
        STATE current_state = STATE::generateState(best_state);
        if(current_state.score > best_state.score) {
            swap(best_state, current_state);
            swap_counter++;
        }
        iteration_counter++;
        time_stamp = toki.gettime();
        average_time = (time_stamp - start_time) / iteration_counter;
    }
    cerr << "Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
    return best_state;
}

template<class STATE>
STATE IterationControl<STATE>::anneal(double time_limit, double temp_start, double temp_end, STATE initial_state) {
    start_time = toki.gettime();
    average_time = 0;
    STATE best_state = initial_state;
    double elapsed_time = 0;
    cerr << "Starts annealing...\n";
    while(elapsed_time + average_time < time_limit) {
        double normalized_time = elapsed_time / time_limit;
        double temp_current = pow(temp_start, 1.0 - normalized_time) * pow(temp_end, normalized_time);
        STATE current_state = STATE::generateState(best_state);
        long long delta = current_state.score - best_state.score;
        if(delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current)) ) {
            swap(best_state, current_state);
            swap_counter++;
        }
        iteration_counter++;
        elapsed_time = toki.gettime() - start_time;
        average_time = elapsed_time / iteration_counter;
    }
    cerr << "Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n";
    return best_state;
}

#endif
#include <iostream>
using namespace std;
using namespace common;

int main() {

    read();

    IterationControl<State> sera;
    State stat = sera.climb(1.8, State::initState());

    stat.print();
    cerr << "my score = " << stat.score << endl;

}
0