結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー breso
提出日時 2025-02-25 22:28:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,903 ms / 2,000 ms
コード長 5,007 bytes
コンパイル時間 4,833 ms
コンパイル使用メモリ 320,012 KB
実行使用メモリ 6,820 KB
スコア 4,793,929
最終ジャッジ日時 2025-02-25 22:30:32
合計ジャッジ時間 103,815 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
    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,ll &max_diff, int &max_diff_cnt){
    max_diff = 0;
    max_diff_cnt = 0;
    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;
            if(dist(a[i][j], ans[i][j])>max_diff){
                max_diff = dist(a[i][j], ans[i][j]);
                max_diff_cnt = 1;
            }else if(dist(a[i][j], ans[i][j])==max_diff){
                max_diff_cnt++;
            }
        }
    }
}

ll score(ll diff,int cnt){
    return diff*10 + cnt;
}

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];
    ll first_diff = 0;
    int cnt = 0;
    make_tower(ans,first_diff,cnt);
    double T_first = 10.0, T_last = 0.01;
    double T = T_first;
    vector<vector<int>> tmp_ans(n, vector<int>(n,0)),last_visited(n,vector<int>(n,0));
    queue<pair<pint,int>> que;
    int cnt_now = 0;
    ll diff = 0;
    int roup_cnt = 0;
    while (!tkd.isTimeOver()) {
        int i = rnd.nextInt(n);
        tmp_ans = ans;  
        if(rnd.nextInt(2)){
            tmp_ans[n-1][i]++;
            if(tmp_ans[n-1][i]>=mod) tmp_ans[n-1][i] -= mod;
            make_tower(tmp_ans,diff,cnt_now);
            int d_sc = score(diff,cnt_now) - score(first_diff,cnt);
            if(d_sc < 0 || exp(-d_sc/T) > rnd.nextDouble()){
                ans = tmp_ans;
                first_diff = diff;
                cnt = cnt_now;
            }
        }else{
            tmp_ans[n-1][i]--;
            if(tmp_ans[n-1][i]<0) tmp_ans[n-1][i] += mod;
            make_tower(tmp_ans,diff,cnt_now);
            int d_sc = score(diff,cnt_now) - score(first_diff,cnt);
            if(d_sc < 0 || exp(-d_sc/T) > rnd.nextDouble()){
                ans = tmp_ans;
                first_diff = diff;
                cnt = cnt_now;
            }
        }
        tkd.setNowTime();
        T = T_first + (T_last - T_first) * tkd.getNowTime() / max_time;
        // cerr<<T<<" "<<first_diff<<" "<<cnt<<endl;
        roup_cnt++;
    }
    rep(i,n){
        cout<<ans[n-1][i]<<" ";
    }
    cout<<endl;
}
0