結果

問題 No.5021 Addition Pyramid
ユーザー soto800
提出日時 2025-03-16 10:25:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,504 ms / 2,000 ms
コード長 5,399 bytes
コンパイル時間 2,609 ms
コンパイル使用メモリ 229,588 KB
実行使用メモリ 7,324 KB
スコア 27,023,351
最終ジャッジ日時 2025-03-16 10:27:16
合計ジャッジ時間 82,057 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 最適化オプションを調整
#pragma GCC optimize("O2")
// #pragma GCC target("avx2") // 問題の原因となる可能性があるため削除または変更
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define REP(i, s, n) for (int i = s; i < n; i++)
#define INF (1 << 28)
#define mp(a, b) make_pair(a, b)
#define SORT(V) sort(V.begin(), V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) #VariableName
#define LOG1(x)                                                                \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << endl;
#define LOG2(x, y)                                                             \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
         << endl;
#define LOG3(x, y, z)                                                          \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \
         << " " << TO_STRING(z) << "=" << z << endl;
#define LOG4(w, x, y, z)                                                       \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << endl;
#define LOG5(w, x, y, z, a)                                                    \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << " " << TO_STRING(a) << "=" << a << endl;
#define LOG6(w, x, y, z, a, b)                                                 \
  if (DEBUG)                                                                   \
    cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \
         << " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \
         << " " << TO_STRING(a) << "=" << a << " " << TO_STRING(b) << "=" << b \
         << endl;

#define overload6(a, b, c, d, e, f, g, ...) g
#define LOG(...)                                                               \
  overload6(__VA_ARGS__, LOG6, LOG5, LOG4, LOG3, LOG2, LOG1)(__VA_ARGS__)

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

uint64_t rand64() {
  static uint64_t x = 88172645463325252ULL;
  x = x ^ (x << 7);
  return x = x ^ (x >> 9);
}

double rand_p() { return rand64() * (1.0 / UINT64_MAX); }

#define LOCAL
#define DEBUG 0
std::chrono::system_clock::time_point start, endTime;

const int MOD = 100000000;

// 誤差を計算する関数
int calculateError(int a, int b) {
  int diff = abs(a - b);
  return min(diff, MOD - diff);
}

int main() {

  int N;
  cin >> N;

  // 目標値を格納
  vector<vector<int>> a(N + 1, vector<int>(N + 1));
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      cin >> a[i][j];
    }
  }

  // 最下段の初期値（すべて0）
  vector<int> c(N + 1, 0);

  // 実際のピラミッド値を計算
  vector<vector<int>> b(N + 1, vector<int>(N + 1, 0));

  // 単純な初期解: 最下段にランダムな値を設定
  for (int i = 1; i <= N; i++) {
    c[i] = rand() % MOD;
  }

  // ランダムに探索を繰り返して良い解を見つける
  int best_max_error = MOD;
  vector<int> best_c = c;

  start = std::chrono::system_clock::now();

  const int MAX_ITERATIONS = 10000000; // 制限時間内に収まる程度の反復回数

  for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
    // 最下段の値を使ってピラミッドを構築
    for (int i = 1; i <= N; i++) {
      b[N][i] = c[i];
    }

    // 下から上に向かってピラミッドを構築
    for (int i = N - 1; i >= 1; i--) {
      for (int j = 1; j <= i; j++) {
        b[i][j] = (b[i + 1][j] + b[i + 1][j + 1]) % MOD;
      }
    }

    // 各マスの誤差を計算し、最大誤差を見つける
    int max_error = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= i; j++) {
        int error = calculateError(a[i][j], b[i][j]);
        max_error = max(max_error, error);
      }
    }

    // 最大誤差が改善されたら更新
    if (max_error < best_max_error) {
      best_max_error = max_error;
      best_c = c;
    }

    // 次の試行のために最下段の一部をランダムに変更
    int pos = 1 + rand() % N;
    c[pos] = rand() % MOD;

    // 時間を確認して制限に近づいたら終了
    endTime = std::chrono::system_clock::now();
    double elapsed =
        std::chrono::duration_cast<std::chrono::milliseconds>(endTime - start)
            .count() /
        1000.0;
    if (elapsed > 1.5)
      break; // 時間制限に余裕を持たせる
  }

  // 最良の結果を出力
  for (int i = 1; i <= N; i++) {
    cout << best_c[i] << endl;
  }

  return 0;
}
0