結果

問題 No.5021 Addition Pyramid
ユーザー colun
提出日時 2025-03-21 17:00:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 2,667 bytes
コンパイル時間 1,268 ms
コンパイル使用メモリ 108,308 KB
実行使用メモリ 7,328 KB
スコア 18,453,555
最終ジャッジ日時 2025-03-21 17:00:11
合計ジャッジ時間 7,490 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <random>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;

const int MOD = 100000000;
const int ITERATIONS = 10000; // 乱択の試行回数（必要に応じて調整可能）

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    // ターゲットとなるピラミッドの値を三角形状に読み込む
    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];
        }
    }
    
    // 乱数生成器の用意
    random_device rd;
    mt19937 rng(rd());
    uniform_int_distribution<int> uni(0, MOD - 1);
    
    int best_error = MOD;  // 最良候補の最大誤差（初期値は十分大きく）
    vector<int> best_bottom(N);  // 最良候補の最下段の数列
    
    // ITERATIONS 回の乱択試行
    for (int iter = 0; iter < ITERATIONS; iter++){
        // 最下段の値 c[0..N-1] を乱数で生成
        vector<int> bottom(N);
        for (int i = 0; i < N; i++){
            bottom[i] = uni(rng);
        }
        
        // ピラミッドの再構築（最下段から上に向かって計算）
        vector<vector<int>> pyramid(N);
        pyramid[N - 1] = bottom;
        for (int i = N - 2; i >= 0; i--){
            pyramid[i].resize(i + 1);
            for (int j = 0; j <= i; j++){
                long long sum = static_cast<long long>(pyramid[i + 1][j]) + pyramid[i + 1][j + 1];
                pyramid[i][j] = sum % MOD;
            }
        }
        
        // 各セルの誤差を計算し，その最大値を求める
        int max_error = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j <= i; j++){
                int diff = abs(pyramid[i][j] - target[i][j]);
                int err = min(diff, MOD - diff);
                max_error = max(max_error, err);
            }
        }
        
        // 現在の候補がこれまでの最良候補より誤差が小さければ更新
        if(max_error < best_error){
            best_error = max_error;
            best_bottom = bottom;
        }
    }
    
    // スコア計算 (5×10⁷ - 最大誤差)
    int score = 50000000 - best_error;
    // デバッグ用に最良の結果を標準エラー出力へ表示
    cerr << "Best max error: " << best_error << "\n";
    cerr << "Score: " << score << "\n";
    
    // 最良の最下段の数列を出力
    for (int i = 0; i < N; i++){
        cout << best_bottom[i] << (i + 1 == N ? "\n" : " ");
    }
    
    return 0;
}
0