結果
問題 | No.5021 Addition Pyramid |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }