結果

問題 No.5021 Addition Pyramid
ユーザー breso
提出日時 2025-02-25 21:05:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,903 ms / 2,000 ms
コード長 5,374 bytes
コンパイル時間 3,922 ms
コンパイル使用メモリ 296,608 KB
実行使用メモリ 6,824 KB
スコア 2,373,477
最終ジャッジ日時 2025-02-25 21:07:21
合計ジャッジ時間 102,900 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #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;
    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(){
    TimeKeeperDouble tkd(1900);
    vector<vector<int>> ans(n,vector<int>(n,0));
    ans[n-1] = a[n-1];
    make_tower(ans);
    double T_first = 60.0, T_last = 0.01;
    double T = T_first;
    // int first_diff = 0;
    vector<vector<int>> diff(n, vector<int>(n,0));
    queue<pint> que;
    int 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-1){
                        if(diff[x-1][y]==0) que.push({x-1,y});
                        diff[x-1][y] += diff[x][y];
                    }
                    if(y+1<x-1){
                        if(diff[x-1][y+1]==0) que.push({x-1,y+1});
                        diff[x-1][y+1] += diff[x][y];
                    }
                }
                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);
            }
        }else{
            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-1){
                        if(diff[x-1][y]==0) que.push({x-1,y});
                        diff[x-1][y] += diff[x][y];
                    }
                    if(y+1<x-1){
                        if(diff[x-1][y+1]==0) que.push({x-1,y+1});
                        diff[x-1][y+1] += diff[x][y];
                        
                    }
                }
                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);
            }
        }
        tkd.setNowTime();
        T = T_first + (T_last - T_first) * tkd.getNowTime() / 1900;
        // cerr<<T<<"\n";
    }
    rep(i,n){
        cout<<ans[n-1][i]<<" ";
    }
    cout<<endl;
}
0