結果

問題 No.5021 Addition Pyramid
ユーザー colun
提出日時 2025-03-21 14:44:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,204 bytes
コンパイル時間 1,344 ms
コンパイル使用メモリ 108,472 KB
実行使用メモリ 7,324 KB
スコア 11,940,518
最終ジャッジ日時 2025-03-21 14:44:52
合計ジャッジ時間 3,675 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <random>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <cassert>

using namespace std;

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 = 10000000;
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(){
    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;
    for(int i=0; i<100; ++i) {
        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;
}
0