結果
問題 | No.5021 Addition Pyramid |
ユーザー |
![]() |
提出日時 | 2025-02-25 20:41:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,045 ms / 2,000 ms |
コード長 | 2,775 bytes |
コンパイル時間 | 4,027 ms |
コンパイル使用メモリ | 282,272 KB |
実行使用メモリ | 6,820 KB |
スコア | 2,006,195 |
最終ジャッジ日時 | 2025-02-25 20:42:15 |
合計ジャッジ時間 | 58,391 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> #include<atcoder/modint> using namespace atcoder; using mint=modint; using namespace std; #define rep(i, N) for(i = 0; i < N; i++) #define ll long long /* テスト */ bool test = 0; /*------------焼きなまし------------*/ float TIME_LIMIT=0.995/*[秒]*/; int end_time=TIME_LIMIT*CLOCKS_PER_SEC; int now_time=0; float start_temp=100.0; float end_temp=1.0; float temp,prob; random_device rd; mt19937 gen(rd()); uniform_int_distribution<int> disi(0, 49); uniform_real_distribution<float> disf(0.0, 1.0); int rand_int(void){return disi(gen);} float rand_float(void){return disf(gen);} /*minimize*/ bool simulated_annealing(int now_score,int next_score){ if(now_score>next_score)return 1; temp=start_temp+(end_temp-start_temp)*now_time/end_time; prob=exp((now_score-next_score)/temp); if(prob>rand_float())return 1; return 0; } /*------------------------------------*/ /*-------------パラメータ-------------*/ /* 高さ */ ll N = 50; /* 目標 */ mint A[50][50]; /* ピラミッド */ mint P[50][50]; /*------------------------------------*/ /*---------------入出力---------------*/ /* 入力 */ void input(void) { ll i, j; cin >> N; rep(i, N) rep(j, i + 1) { ll a; cin >> a; A[i][j] = a; } } /* 出力 */ void output(void) { ll i; rep(i, N) cout << P[49][i].val() << " "; cout << endl; } /*------------------------------------*/ /* 状態の計算 */ ll cal(vector<mint>& v) { ll i, j; rep(i, N) { P[N - 1][i] = v[i]; } for(i = N - 2; 0 <= i; i--) { rep(j, i + 1) { P[i][j] = P[i + 1][j] + P[i + 1][j + 1]; } } ll score = 0; rep(i, N) { rep (j, i + 1) { ll diff = A[i][j].val() - P[i][j].val(); diff = max(diff, -diff); diff = min(diff, 100'000'000 - diff); score += diff; } } return score; } /*解く*/ void solve(void){ vector<mint>v(50, 0); ll now = cal(v), next; while(now_time<end_time){ for(ll i = 0; i < 10; i++) { ll id = rand_int(); ll r = rand_int() % 2; if(r == 0) v[id] += 100; else v[id] -= 100; next = cal(v); if(simulated_annealing(now, next)) { now = next; } else { if(r == 0) v[id] -= 100; else v[id] += 100; } } now_time=clock(); } } /* メイン関数 */ int main(int argc, char *argv[]) { if (argc > 1 && string(argv[1]) == "eevee") { test = 1; } /*main関数内で使用,modを設定*/ int mod=100'000'000; mint::set_mod(mod); input(); solve(); output(); return 0; }