結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー Zhiyuan Chen
提出日時 2025-02-25 21:03:40
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 4,087 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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 #
raw source code 

#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