結果

問題 No.5021 Addition Pyramid
ユーザー SnowBeenDiding
提出日時 2025-03-21 14:49:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,903 ms / 2,000 ms
コード長 4,045 bytes
コンパイル時間 4,250 ms
コンパイル使用メモリ 283,500 KB
実行使用メモリ 7,328 KB
スコア 1,832,078
最終ジャッジ日時 2025-03-21 14:51:36
合計ジャッジ時間 103,550 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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;
using EvalResult = tuple<int, double, double, double, double>;

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];
    EvalResult bestEval;
    double bestMetric;
    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;
    }

    EvalResult evaluate() {
        EvalResult r = {0, 0, 0, 0, 0};
        for (int i = 0; i < N; i++)
            for (int j = 0; j <= i; j++) {
                int diff =
                    min(abs(a[i][j] - b[i][j]), MOD - abs(a[i][j] - b[i][j]));
                get<1>(r) += diff;
                get<2>(r) += 1.0 * diff * diff;
                get<3>(r) += 1.0 * diff * diff * diff;
                get<4>(r) += 1.0 * diff * diff * diff * diff;
                get<0>(r) = max(get<0>(r), diff);
            }
        return r;
    }

    double metric(const EvalResult &r, double elapsed) const {
        double frac = min(elapsed / params.timeLimit, 1.0);
        if (frac < 0.25)
            return get<1>(r);
        if (frac < 0.50)
            return get<2>(r);
        if (frac < 0.75)
            return get<3>(r);
        return get<4>(r);
    }

    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();
        EvalResult curEval = evaluate();
        double curMetric = metric(curEval, 0);
        bestEval = curEval;
        bestMetric = curMetric;
        memcpy(best, cur, sizeof(cur));
        double T = params.T0;

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

            int pos = uni_pos(rng);
            int old = cur[pos];
            cur[pos] = (old + uni_delta(rng) + MOD) % MOD;
            build();
            EvalResult newEval = evaluate();
            double newMetric = metric(newEval, elapsed);
            double diff = newMetric - curMetric;
            if (diff < 0 || exp(-diff / T) > uni_real(rng)) {
                curEval = newEval;
                curMetric = newMetric;
                int newMax = get<0>(newEval), bestMax = get<0>(bestEval);
                if (newMax < bestMax) {
                    bestEval = newEval;
                    memcpy(best, cur, sizeof(cur));
                    bestMetric = newMetric;
                }
            } 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: " << get<0>(bestEval) << "\n";
        cerr << "Score: " << (50000000 - get<0>(bestEval)) << "\n";
    }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    PyramidSolver().solve();
    return 0;
}
0