結果

問題 No.5021 Addition Pyramid
ユーザー soto800
提出日時 2025-03-16 10:54:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,805 ms / 2,000 ms
コード長 7,420 bytes
コンパイル時間 3,305 ms
コンパイル使用メモリ 233,348 KB
実行使用メモリ 7,328 KB
スコア 50,101,548
最終ジャッジ日時 2025-03-16 10:55:49
合計ジャッジ時間 96,668 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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] = rand64() % MOD;
  }

  // 初期状態のピラミッドを構築
  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 best_max_error = MOD;
  vector<int> best_c = c;

  start = std::chrono::system_clock::now();
  const int MAX_ITERATIONS = 10000000; // 制限時間内に収まる程度の反復回数

  // 焼きなまし法のパラメータ - 時間ベースに変更
  double startTemp = 10.0;       // 初期温度
  double endTemp = 0.0001;       // 最終温度
  const double TIME_LIMIT = 1.8; // 制限時間（秒）

  int cnt = 0;
  int current_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]);
      current_max_error = max(current_max_error, error);
    }
  }

  for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
    cnt++;

    // 経過時間に基づく進捗度の計算
    endTime = std::chrono::system_clock::now();
    double elapsed =
        std::chrono::duration_cast<std::chrono::milliseconds>(endTime - start)
            .count() /
        1000.0;
    double progress = min(1.0, elapsed / TIME_LIMIT); // 0.0〜1.0の範囲

    // 進捗に応じて温度を線形に変化
    double temp = startTemp + (endTemp - startTemp) * progress;

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

    // 変更された位置から上に向かって、影響を受ける部分だけを更新
    b[N][pos] = new_val; // 最下段の更新

    // 上に向かって影響する部分だけ更新
    for (int i = N - 1; i >= 1; i--) {
      for (int j = max(1, pos - (N - i)); j <= min(i, pos); 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);
      }
    }

    // 焼きなまし法による判定
    bool accept = false;

    if (max_error <= current_max_error) {
      // 改善された場合は常に受け入れる
      accept = true;
    } else {
      // 改善されなかった場合は確率的に受け入れる
      double delta = max_error - current_max_error;
      double probability = exp(-delta / temp);
      if (rand_p() < probability) {
        accept = true;
      }
    }

    if (accept) {
      // 変更を受け入れる
      current_max_error = max_error;

      // 最良解更新
      if (max_error < best_max_error) {
        best_max_error = max_error;
        best_c = c;
      }
    } else {
      // 変更をロールバック
      c[pos] = old_val;
      b[N][pos] = old_val;

      // ロールバックに伴いピラミッドも元に戻す
      for (int i = N - 1; i >= 1; i--) {
        for (int j = max(1, pos - (N - i)); j <= min(i, pos); j++) {
          b[i][j] = (b[i + 1][j] + b[i + 1][j + 1]) % MOD;
        }
      }
    }

    // 時間制限に近づいたら終了
    if (elapsed > TIME_LIMIT) {
      break;
    }
  }

  std::cerr << "cnt:" << cnt << " best_error:" << best_max_error << endl;

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

  return 0;
}
0