結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー SnowBeenDiding
提出日時 2025-03-21 14:26:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,435 ms / 2,000 ms
コード長 3,072 bytes
コンパイル時間 3,361 ms
コンパイル使用メモリ 278,352 KB
実行使用メモリ 7,324 KB
スコア 1,823,780
最終ジャッジ日時 2025-03-21 14:27:41
合計ジャッジ時間 76,421 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

static const int N = 50;
static const int MOD = 100000000;
typedef long long ll;

struct SAParams {
    double T0 = 1e4;
    double Tend = 1e-4;
    double alpha = 0.99995;
    double timeLimit = 1.9;
    int deltaRange = 1000000;
};

struct PyramidSolver {
    int a[N][N], b[N][N];
    int cur[N], best[N];
    int bestScore;
    SAParams params;
    mt19937_64 rng;
    uniform_int_distribution<int> uni_pos;
    uniform_int_distribution<int> uni_delta;
    uniform_real_distribution<double> uni_real;

    PyramidSolver()
        : rng(chrono::high_resolution_clock::now().time_since_epoch().count()),
          uni_pos(0, N - 1), uni_delta(-params.deltaRange, params.deltaRange),
          uni_real(0.0, 1.0) {}

    void readInput() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j <= i; j++)
                cin >> a[i][j];
    }

    void build() {
        for (int j = 0; j < N; j++)
            b[N - 1][j] = (cur[j] % MOD + MOD) % MOD;
        for (int i = N - 2; i >= 0; i--)
            for (int j = 0; j <= i; j++)
                b[i][j] = (b[i + 1][j] + b[i + 1][j + 1]) % MOD;
    }

    int evaluate() {
        int mx = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j <= i; j++) {
                int diff = abs(a[i][j] - b[i][j]);
                mx = max(mx, min(diff, MOD - diff));
            }
        return mx;
    }

    void anneal() {
        auto start = chrono::high_resolution_clock::now();
        for (int i = 0; i < N; i++)
            cur[i] = uniform_int_distribution<int>(0, MOD - 1)(rng);
        build();
        int curScore = evaluate();
        memcpy(best, cur, sizeof(cur));
        bestScore = curScore;
        double T = params.T0;

        while (true) {
            auto now = chrono::high_resolution_clock::now();
            if (chrono::duration<double>(now - start).count() >=
                    params.timeLimit ||
                T <= params.Tend)
                break;

            int pos = uni_pos(rng);
            int old = cur[pos];
            cur[pos] = (old + uni_delta(rng) + MOD) % MOD;
            build();
            int newScore = evaluate();
            int diff = newScore - curScore;
            if (diff < 0 || exp(-diff / T) > uni_real(rng)) {
                curScore = newScore;
                if (newScore < bestScore) {
                    bestScore = newScore;
                    memcpy(best, cur, sizeof(cur));
                }
            } else {
                cur[pos] = old;
            }
            T *= params.alpha;
        }
    }

    void output() const {
        for (int i = 0; i < N; i++)
            cout << best[i] << (i + 1 < N ? ' ' : '\n');
        cerr << "Max Error: " << bestScore << '\n';
        cerr << "Score: " << (50000000 - bestScore) << '\n';
    }

    void solve() {
        readInput();
        anneal();
        output();
    }
};

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

    PyramidSolver solver;
    solver.solve();
    return 0;
}
0