結果

問題 No.5021 Addition Pyramid
ユーザー Zhiyuan Chen
提出日時 2025-02-25 21:03:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 4,087 bytes
コンパイル時間 1,094 ms
コンパイル使用メモリ 97,908 KB
実行使用メモリ 6,820 KB
スコア 34,939,989
最終ジャッジ日時 2025-02-25 21:03:49
合計ジャッジ時間 9,659 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;

const int MOD = 100000000; // 模 10^8

// 计算模意义下 a 与 b 的距离(取 |a-b| 和 MOD - |a-b| 中较小值)
inline int modDiff(int a, int b) {
    int diff = abs(a - b);
    return min(diff, MOD - diff);
}

// 根据底层数字 bottom,利用加法金字塔的递推关系(从下向上)计算整座金字塔,
// 并返回其中最大的误差(与目标金字塔 target 对比)
int compute_max_error(const vector<int> &bottom, const vector<vector<int>> &target, int N) {
    // dp[i][j] 表示金字塔第 i 行(0-index,对应题中第 i+1 层)第 j 个数字
    // dp[N-1] 就是底层(第 N 层)的数字
    vector<vector<int>> dp(N);
    dp[N-1] = bottom; // 底层初始化

    // 自下而上计算金字塔中每个位置:dp[i][j] = (dp[i+1][j] + dp[i+1][j+1]) mod MOD
    for (int i = N - 2; i >= 0; i--) {
        dp[i].resize(i + 1);
        for (int j = 0; j <= i; j++) {
            dp[i][j] = ( (long long)dp[i+1][j] + dp[i+1][j+1] ) % MOD;
        }
    }
    
    // 计算与目标金字塔 target 的最大误差
    int maxErr = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            int err = modDiff(dp[i][j], target[i][j]);
            maxErr = max(maxErr, err);
        }
    }
    return maxErr;
}

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

    int N;
    cin >> N;
    // 读入完整的金字塔目标值,共有 N 行,第 i 行 i 个数字
    vector<vector<int>> target(N);
    for (int i = 0; i < N; i++) {
        target[i].resize(i + 1);
        for (int j = 0; j <= i; j++) {
            cin >> target[i][j];
        }
    }
    
    // 初始解:取目标金字塔底层(第 N 行)的数字作为底层解
    vector<int> bottom = target[N-1];

    // 计算当前解的最大误差
    int bestError = compute_max_error(bottom, target, N);
    
    // 启发式调整(简单的 hill climbing / 模拟退火思路)
    // 下面的迭代次数可以根据需要调节
    const int ITER_MAX = 20000;
    // 初始步长:设为 MOD/100
    double initStep = MOD / 100.0; 
    // 使用随机数生成器
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    // 每次随机选择一个底层数字位置,尝试进行随机微调
    for (int iter = 0; iter < ITER_MAX; iter++) {
        // 动态降低步长(可理解为退火过程),保证随着迭代步幅逐渐变小
        double curStep = initStep * (1.0 - (double)iter / ITER_MAX);
        if(curStep < 1) curStep = 1;
        // 选择底层位置
        uniform_int_distribution<int> posDist(0, N - 1);
        int pos = posDist(rng);
        // 选择调整值,范围大致为 [-curStep, curStep]
        uniform_int_distribution<int> deltaDist(- (int)curStep, (int)curStep);
        int delta = deltaDist(rng);
        
        // 保存旧值
        int oldVal = bottom[pos];
        // 更新该位置(注意保证在 [0, MOD) 内)
        int newVal = (oldVal + delta) % MOD;
        if(newVal < 0) newVal += MOD;
        bottom[pos] = newVal;
        
        // 计算调整后的最大误差
        int newError = compute_max_error(bottom, target, N);
        // 如果调整有利,则接受改动;否则恢复原值
        if(newError < bestError) {
            bestError = newError;
            // 可以在此处输出一些调试信息,例如 iter, bestError 等
            // cerr << "Iter " << iter << ": Improved max error to " << bestError << "\n";
            // 若达到完美匹配可以提前退出
            if(bestError == 0) break;
        } else {
            // 恢复回去
            bottom[pos] = oldVal;
        }
    }
    
    // 输出最终的底层数字(题目规定每行输出一个数字,共 N 个)
    // 注意输出顺序为左到右(即 bottom[0] 到 bottom[N-1])
    for (int i = 0; i < N; i++) {
        cout << bottom[i] << "\n";
    }
    return 0;
}
0