結果

問題 No.5021 Addition Pyramid
ユーザー e869120
提出日時 2025-02-24 22:57:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 920 ms / 2,000 ms
コード長 5,024 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 87,908 KB
実行使用メモリ 6,820 KB
スコア 393,159,547
最終ジャッジ日時 2025-02-25 19:33:17
合計ジャッジ時間 49,516 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MAX = 100000000;
unsigned int seed = 869120;

// ===========================================================================================================
// === Basic Part
// ===========================================================================================================
unsigned int Rand() {
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

double GetTime() {
    return 1.0 * clock() / CLOCKS_PER_SEC;
}

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

int score_function(int N, vector<vector<int>> A, vector<int> C) {
    vector<vector<int>> B(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) B[N - 1][i] = C[i];
    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]) % 100000000;
    }
    int max_error = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) max_error = max(max_error, min(abs(A[i][j] - B[i][j]), 100000000 - abs(A[i][j] - B[i][j])));
    }
    return 50000000 - max_error;
}


// ===========================================================================================================
// === DFS Function
// ===========================================================================================================
int min_range[24];
int max_range[24];

vector<int> dfs(int N, int row, int border, double start_time, vector<vector<int>>& A, vector<vector<int>>& C) {
    if ((GetTime() - start_time) > 0.9) return vector<int>{-2};
    if (row == N) return C[N - 1];

    // Get Initial Answer
    vector<int> curr_row = C[row];
    curr_row[0] = 0;
    for (int i = 1; i <= row; i++) curr_row[i] = (C[row - 1][i - 1] - curr_row[i - 1] + MAX) % MAX;

    // Get Worst Position
    for (int i = 0; i < 24; i++) min_range[i] = MAX;
    for (int i = 0; i < 24; i++) max_range[i] = -1;
    for (int i = 0; i <= row; i++) {
        int opposite = A[row][i] + MAX / 2;
        int worst = (i % 2 == 0 ? (opposite - curr_row[i] + MAX) % MAX : (curr_row[i] - opposite + MAX + MAX) % MAX);
        int index = (worst >> 22);
        min_range[index] = min(min_range[index], worst);
        max_range[index] = max(max_range[index], worst);
    }
    
    // Search Good Position
    vector<pair<int, int>> good;
    int cx = 0, last = -1;
    while (true) {
        if (min_range[cx % 24] == MAX) { cx++; continue; }
        if (last != -1) {
            int cl = last + border;
            int cr = min_range[cx % 24] - border; if (cx >= 24) cr += MAX;
            if (cl < cr) good.emplace_back(make_pair(cl, cr));
        }
        if (cx >= 24) break;
        last = max_range[cx % 24]; cx++;
    }
    if (good.size() == 0) return vector<int>{-1};

    // Pick Good Position Randomly
    for (int loops = 1; loops <= 35; loops++) {
        int idx = Rand() % good.size();
        int val = Rand() % (good[idx].second - good[idx].first + 1) + good[idx].first;
        if (val >= MAX) val -= MAX;

        // Recursion
        C[row][0] = val;
        for (int i = 1; i <= row; i++) C[row][i] = (C[row - 1][i - 1] - C[row][i - 1] + MAX) % MAX;
        vector<int> ans = dfs(N, row + 1, border, start_time, A, C);
        if (ans != vector<int>{-1}) return ans;
    }
    return vector<int>{-1};
}



// ===========================================================================================================
// === Solve Function
// ===========================================================================================================
vector<int> solver(int N, vector<vector<int>> A) {
    double start_time = GetTime();
    int best_score = -1;
    vector<int> best_ans;

    // DFS Search Start
    for (int border = 4400000; border <= 10000000; border += 200000) {
        cerr << border << endl;
        vector<vector<int>> C(N, vector<int>(N, 0));
        C[0][0] = A[0][0];
        vector<int> ret = dfs(N, 1, border, start_time, A, C);
        if (ret == vector<int>{-2}) break;
        if (ret.size() == N) {
            int cand_score = score_function(N, A, ret);
            if (best_score < cand_score) {
                best_score = cand_score;
                best_ans = ret;
            }
        }
    }

    // Return
    // cerr << best_score << endl;
    return best_ans;
}


// ===========================================================================================================
// === Main Function
// ===========================================================================================================
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 = solver(N, A);
    for (int i = 0; i < N; i++) {
        if (i >= 1) cout << " ";
        cout << Answer[i];
    }
    cout << endl;
    return 0;
}
0