#1057013 (C++17) No.5021 Addition Pyramid

• 問題: No.5021 Addition Pyramid
• ユーザー: colun
• 提出日時: 2025-03-21 14:52:15
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,903 ms / 2,000 ms
• コード長: 6,800 bytes
• コンパイル時間: 1,396 ms
• コンパイル使用メモリ: 108,264 KB
• 実行使用メモリ: 7,328 KB
• スコア: 49,005,774
• 最終ジャッジ日時: 2025-03-21 14:53:56
• 合計ジャッジ時間: 100,671 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
other	AC * 50

ソースコード

#include <iostream>
#include <vector>
#include <random>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <cassert>
#include <sys/time.h>

using namespace std;

inline void getCpuClock(unsigned long long & t) {
#if __emscripten__
    t = std::chrono::high_resolution_clock::now().time_since_epoch().count();
#else
    __asm__ __volatile__ ("rdtsc" : "=a"(*(unsigned int*)&t), "=d"(((unsigned int*)&t)[1]));
#endif
}
inline unsigned long long getCpuClock() {
    unsigned long long t;
    getCpuClock(t);
    return t;
}
inline double getNativeTime() {
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}
unsigned long long getTime$initCpuClock;
unsigned long long getTime$reserveUpdateCpuClock;
double getTime$initNativeTime;
double getTime$secPerClock;
double getTime$doneTime;
inline void initTime() {
    getTime$initNativeTime = getNativeTime();
    getCpuClock(getTime$initCpuClock);
    getTime$secPerClock = 0.00000000025;
    getTime$reserveUpdateCpuClock = 10000000;
    getTime$doneTime = 0;
}
struct getTime$init_class {
    inline getTime$init_class() {
        initTime();
    }
};
getTime$init_class getTime$init_obj;

#if __local__
double getTime$revRate = 1.0;
double getTime$rate = 1.0;
bool getTime$stopFlag = false;
double getTime$correct = 0.0;
#endif
#if __local__
inline void setLocalTimeRate(double rate) {
    getTime$rate = rate;
    getTime$revRate = 1.0 / rate;
}
#else
#define setLocalTimeRate(...)
#endif

inline double getTime() {
#if __local__
    if(getTime$stopFlag) {
        return getTime$doneTime;
    }
#endif
    unsigned long long now;
    getCpuClock(now);
    now -= getTime$initCpuClock;
    if(getTime$reserveUpdateCpuClock < now) {
        double nowTime = getNativeTime() - getTime$initNativeTime;
        getTime$secPerClock = nowTime / now;
        getTime$reserveUpdateCpuClock = now + (unsigned long long)(0.05 * now / nowTime);
    }
#if __local__
    return (getTime$doneTime = std::fmax(getTime$doneTime, getTime$secPerClock * now * getTime$revRate + getTime$correct));
#else
    return getTime$doneTime = std::fmax(getTime$doneTime, getTime$secPerClock * now);
#endif
}
inline void getTimeStop() {
#if __local__
    if(!getTime$stopFlag) {
        getTime();
        getTime$stopFlag = true;
    }
#endif
}
inline void getTimeStart() {
#if __local__
    if(getTime$stopFlag) {
        double before = getTime();
        getTime$stopFlag = false;
        double after = getTime();
        getTime$correct += before - after;
        getTime$doneTime = before;
    }
#endif
}
#if __local__
inline void setTime(double t) {
    getTime$correct += t - getTime();
    getTime$doneTime = t;
}
#else
#define setTime(...)
#endif

inline unsigned int asm_mul_hi(unsigned int x, unsigned int y) {
    __asm__ __volatile__("mul %%edx" : "+a"(x), "+d"(y));
    return y;
}
unsigned long long mrand49$state = 0x8a5cd789635d2dffULL;
inline int mrand49() {
    mrand49$state *= 6364136223846793005ULL;
    mrand49$state += 1442695040888963407ULL;
    unsigned int ret = ((mrand49$state>>18)^mrand49$state) >> 27;
    unsigned int rot = (mrand49$state>>59);
    return (ret>>rot) | (ret<<-rot);
}
inline int lrand49(int r) {
    assert(1<=r);
    return asm_mul_hi(mrand49(), r);
}
inline double drand49() {
    return ((unsigned int)mrand49() + 0.5) * (1.0/4294967296.0);
}

struct SO {
    bool first;
    int turn;
    int use_turn;
    union choice {
        int i;
        double f;
    };
    double best_score;
    std::vector<choice> best;
    choice change_value;

    void init() {
        use_turn = 0;
        best_score = -DBL_MAX;
        best.clear();
    }
    void begin() {
        turn = 0;
        if(best.size()) {
            use_turn = lrand49(best.size());
        }
        else {
            use_turn = 0;
        }
        if(best.size()<=use_turn) {
            use_turn = 0;
        }
    }
    int oracle(int n) {
        if(best.size() <= turn) {
            int ret = lrand49(n);
            best.emplace_back();
            best.back().i = ret;
            if(turn==use_turn) {
                change_value = best.back();
            }
            ++turn;
            return ret;
        }
        else if(turn!=use_turn) {
            return best[turn++].i;
        }
        else {
            ++turn;
            change_value.i = lrand49(n);
            return change_value.i;
        }
    }
    bool end(double score) {
        first = false;
        if(best_score < score) {
            best_score = score;
            best[use_turn] = change_value;
            return true;
        }
        return false;
    }
};
SO so;

const int MOD = 100000000;

vector<int> bottom;
vector<int> best_bottom;
vector<vector<int>> target;
int N;
int max_error;
int best_max_error;

int W = 5000000;
int halfW = W / 2;

int sim() {
    bottom.resize(N);
    // 最下段の値 c[0..N-1] を乱数で生成
    for (int i = 0; i < N; i++){
        bottom[i] = (target[N-1][i] + so.oracle(W) - halfW + MOD) % MOD;
    }
    
    // ピラミッドを最下段から上へ再構築
    vector<vector<int>> pyramid(N);
    pyramid[N - 1] = bottom;
    for (int i = N - 2; i >= 0; i--){
        pyramid[i].resize(i + 1);
        for (int j = 0; j <= i; j++){
            long long sum = static_cast<long long>(pyramid[i + 1][j]) + pyramid[i + 1][j + 1];
            pyramid[i][j] = sum % MOD;
        }
    }
    
    // 各セルの誤差を計算し，その最大値を求める
    max_error = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j <= i; j++){
            int diff = abs(pyramid[i][j] - target[i][j]);
            int err = min(diff, MOD - diff);
            max_error = max(max_error, err);
        }
    }
    
    // スコア計算 (5×10⁷ - 最大誤差)
    return 50000000 - max_error;
}

int main(){
    initTime();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    
    // ターゲットのピラミッド値を三角形状に読み込む
    target.resize(N);
    for (int i = 0; i < N; i++){
        target[i].resize(i + 1);
        for (int j = 0; j <= i; j++){
            cin >> target[i][j];
        }
    }
    
    int best_score = 0;
    so.init();
    while(getTime() < 1.9) {
        so.begin();
        int sc = sim();
        if(so.end(sc)) {
            best_bottom = bottom;
            best_score = sc;
            best_max_error = max_error;
        }
    }
    // デバッグ用にシミュレーション結果を標準エラー出力へ
    cerr << "MaxError: " << best_max_error << "\n";
    cerr << "Score: " << best_score << "\n";
    
    // 最下段の値を出力
    for (int i = 0; i < N; i++){
        cout << best_bottom[i] << (i + 1 == N ? "\n" : " ");
    }
    
    return 0;
}