結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー colun
提出日時 2025-03-21 14:05:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,942 bytes
コンパイル時間 1,461 ms
コンパイル使用メモリ 105,860 KB
実行使用メモリ 5,888 KB
スコア 2,214,375
最終ジャッジ日時 2025-03-21 14:05:20
合計ジャッジ時間 3,829 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MOD = 100000000;

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);
    
    // 最下段の値 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);
        }
    }
    
    // スコア計算 (5×10⁷ - 最大誤差)
    int score = 50000000 - max_error;
    // デバッグ用にシミュレーション結果を標準エラー出力へ
    cerr << "Max error: " << max_error << "\n";
    cerr << "Score: " << score << "\n";
    
    // 最下段の値を出力
    for (int i = 0; i < N; i++){
        cout << bottom[i] << (i + 1 == N ? "\n" : " ");
    }
    
    return 0;
}
0