結果
| 問題 |
No.5021 Addition Pyramid
|
| コンテスト | |
| ユーザー |
 breso
|
| 提出日時 | 2025-02-25 21:54:04 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,903 ms / 2,000 ms |
| コード長 | 6,129 bytes |
| コンパイル時間 | 3,652 ms |
| コンパイル使用メモリ | 301,680 KB |
| 実行使用メモリ | 6,820 KB |
| スコア | 2,163,658 |
| 最終ジャッジ日時 | 2025-02-25 21:55:51 |
| 合計ジャッジ時間 | 103,068 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;
using ll = long long;
using vecint = std::vector<int>;
using vecll = std::vector<long long>;
using vecstr = std::vector<string>;
using vecbool = std::vector<bool>;
using vecdou = std::vector<double>;
using vecpl = std::vector<pair<ll,ll>>;
using vec2d = std::vector<vecint>;
using pl = pair<long long,long long>;
using pint = pair<int,int>;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rep1(i,n) for (int i = 1; i <= (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define INF 1000000000
#define inr(l,x,r) ((l) <= (x) && (x) < (r))
class TimeKeeperDouble {
private:
std::chrono::high_resolution_clock::time_point start_time_;
double time_threshold_;
double now_time_ = 0;
public:
// 時間制限をミリ秒単位で指定してインスタンスをつくる。
TimeKeeperDouble(const double time_threshold)
: start_time_(std::chrono::high_resolution_clock::now()),
time_threshold_(time_threshold) {}
// 経過時間をnow_time_に格納する。
void setNowTime() {
auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
this->now_time_ =
std::chrono::duration_cast<std::chrono::microseconds>(diff).count() *
1e-3; // ms
}
void changeTimeThreshold(const double time_threshold) {
this->time_threshold_ = time_threshold;
}
// 経過時間をnow_time_に取得する。
double getNowTime() const { return this->now_time_; }
// インスタンス生成した時から指定した時間制限を超過したか判定する。
bool isTimeOver() const { return now_time_ >= time_threshold_; }
};
class Random {
public:
std::mt19937 mt_; // シード0でメルセンヌツイスターの乱数生成器を初期化
// 0以上1.0未満の実数の範囲の乱数生成
uniform_real_distribution<double> dd_{0, 1.0};
// seedを指定して初期化
Random(const int seed = 0) : mt_(std::mt19937(seed)) {}
// 0以上m未満の整数の範囲の乱数
inline int nextInt(const int m) {
uniform_int_distribution<int> di(0, m - 1);
return di(mt_);
}
// 0以上1.0未満の実数の範囲の乱数
inline double nextDouble() { return dd_(mt_); }
// 0以上1.0未満の実数の範囲の乱数のlog。焼きなまし法で使いやすい。
inline double nextLog() { return log(dd_(mt_)); }
};
Random rnd(0);
int mod = 100000000;
int n=50;
vector<vecint> a(50,vecint(50));
int dist(int x,int y) {
x%=mod;
if(x<0) x+=mod;
y%=mod;
if(y<0) y+=mod;
return min(abs(x-y),mod-abs(x-y));
}
void input() {
cin>>n;
rep(i,n) rep(j,i+1) cin>>a[i][j];
}
void solve();
int main() {
input();
solve();
}
void make_tower(vector<vector<int>> &ans){
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
ans[i][j] = ans[i+1][j] + ans[i+1][j+1];
if(ans[i][j]>=mod) ans[i][j] -= mod;
}
}
}
void solve(){
double max_time = 1900;
TimeKeeperDouble tkd(max_time);
vector<vector<int>> ans(n,vector<int>(n,0));
ans[n-1] = a[n-1];
make_tower(ans);
double T_first = 100.0, T_last = 0.01;
double T = T_first;
ll first_diff = 0;
rep(i,n){
rep(j,i+1){
first_diff += dist(a[i][j], ans[i][j]);
}
}
vector<vector<ll>> diff(n, vector<ll>(n,0));
queue<pint> que;
ll d;
while (!tkd.isTimeOver()) {
int i = rnd.nextInt(n);
if(rnd.nextInt(2)){
diff[n-1][i]++;
que.push({n-1,i});
d=0;
while(!que.empty()){
auto [x,y] = que.front(); que.pop();
d += dist(a[x][y], ans[x][y]+diff[x][y]) - dist(a[x][y], ans[x][y]);
if(x>0){
if(y<=x && y>0){
if(diff[x-1][y-1]==0) que.push({x-1,y-1});
diff[x-1][y-1] += diff[x][y];
if(diff[x-1][y-1]>=mod) diff[x-1][y-1] -= mod;
}
if(y<x){
if(diff[x-1][y]==0) que.push({x-1,y});
diff[x-1][y] += diff[x][y];
if(diff[x-1][y]>=mod) diff[x-1][y] -= mod;
}
}
diff[x][y] = 0;
}
if(d<0 || rnd.nextDouble()<exp(-d/T)){
ans[n-1][i] ++;
if(ans[n-1][i]>=mod) ans[n-1][i] -= mod;
make_tower(ans);
first_diff += d;
}
}else{
diff[n-1][i]=mod-1;
que.push({n-1,i});
d=0;
while(!que.empty()){
auto [x,y] = que.front(); que.pop();
d += dist(a[x][y], ans[x][y]+diff[x][y]) - dist(a[x][y], ans[x][y]);
if(x>0){
if(y<=x && y>0){
if(diff[x-1][y-1]==0) que.push({x-1,y-1});
diff[x-1][y-1] += diff[x][y];
if(diff[x-1][y-1]>=mod) diff[x-1][y-1] -= mod;
}
if(y<x){
if(diff[x-1][y]==0) que.push({x-1,y});
diff[x-1][y] += diff[x][y];
if(diff[x-1][y]>=mod) diff[x-1][y] -= mod;
}
}
diff[x][y] = 0;
}
if(d<0 || rnd.nextDouble()<exp(-d/T)){
ans[n-1][i] --;
if(ans[n-1][i]<0) ans[n-1][i] += mod;
make_tower(ans);
first_diff += d;
}
}
tkd.setNowTime();
T = T_first + (T_last - T_first) * tkd.getNowTime() / max_time;
cerr<<T<<" "<<first_diff<<endl;
}
// ll total_diff = 0;
// rep(i,n){
// rep(j,i+1){
// total_diff += dist(a[i][j], ans[i][j]);
// }
// }
// if(total_diff!=first_diff) cout<<"error"<<endl;
// cout<<total_diff<<" "<<first_diff<<endl;
rep(i,n){
cout<<ans[n-1][i]<<" ";
}
cout<<endl;
}