結果

問題 No.5021 Addition Pyramid
ユーザー e869120
提出日時 2025-02-25 22:16:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,845 ms / 2,000 ms
コード長 2,488 bytes
コンパイル時間 2,709 ms
コンパイル使用メモリ 206,512 KB
実行使用メモリ 6,820 KB
スコア 234,337,942
最終ジャッジ日時 2025-02-25 22:18:07
合計ジャッジ時間 97,647 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MAX = 100000000;

int get_error(int a, int b) {
    return min(abs(a - b), MAX - abs(a - b));
}

int get_score(int N, vector<vector<int>> A, vector<vector<int>> C) {
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) res = max(res, get_error(A[i][j], C[i][j]));
    }
    return MAX / 2 - res;
}

vector<int> get_answer(int N, vector<vector<int>> A) {
    int start_time = clock();
    int best_score = -1;
    vector<int> best_ans;
    vector<vector<int>> C(N, vector<int>(N, 0));

    // Loop until 0.5sec
    while (clock() - start_time < 18 * CLOCKS_PER_SEC / 10) {
        C[0][0] = rand() % MAX;

        // Simulation
        for (int row = 1; row <= N - 1; row++) {
            pair<int, int> best_gap = make_pair(-1, -1);
            vector<int> worst;
            C[row][0] = 0;
            for (int i = 1; i <= row; i++) C[row][i] = (C[row - 1][i - 1] - C[row][i - 1] + MAX) % MAX;

            // Get Best Position
            for (int i = 0; i <= row; i++) {
                int opposite = (A[row][i] + MAX / 2) % MAX;
                if (i % 2 == 0) worst.push_back((opposite - C[row][i] + MAX) % MAX);
                if (i % 2 == 1) worst.push_back((C[row][i] - opposite + MAX) % MAX);
            }
            sort(worst.begin(), worst.end());
            for (int i = 0; i < worst.size(); i++) {
                int a1 = worst[i];
                int a2 = (i == worst.size() - 1 ? MAX + worst[0] : worst[i + 1]);
                int mid = (a1 + a2) / 2;
                int gap = a2 - a1;
                best_gap = max(best_gap, make_pair(gap, mid % MAX));
            }

            // Apply
            C[row][0] = best_gap.second;
            for (int i = 1; i <= row; i++) C[row][i] = (C[row - 1][i - 1] - C[row][i - 1] + MAX) % MAX;
        }

        // Get Score
        int cand_score = get_score(N, A, C);
        if (best_score < cand_score) {
            best_score = cand_score;
            best_ans = C[N - 1];
        }
    }

    // Return
    return best_ans;
}

int main() {
    // Step 1. Input
    int N; cin >> N;
    vector<vector<int>> A(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) cin >> A[i][j];
    }

    // Step 2. Solve
    vector<int> Answer = get_answer(N, A);
    for (int i = 0; i < N; i++) {
        if (i >= 1) cout << " ";
        cout << Answer[i];
    }
    cout << endl;
    return 0;
}
0