#1046253 (C++23) No.5021 Addition Pyramid

• 問題: No.5021 Addition Pyramid
• ユーザー: てんぷら
• 提出日時: 2025-02-25 22:59:27
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,265 ms / 2,000 ms
• コード長: 7,614 bytes
• コンパイル時間: 7,173 ms
• コンパイル使用メモリ: 335,560 KB
• 実行使用メモリ: 7,572 KB
• スコア: 324,118,205
• 最終ジャッジ日時: 2025-02-25 23:01:01
• 合計ジャッジ時間: 69,091 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:237:23: warning: ‘void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<State*, vector<State> >]’ is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  237 |         random_shuffle(states.begin(), states.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/atcoder/convolution.hpp:4,
                 from /usr/include/atcoder/convolution:1,
                 from /usr/include/atcoder/all:1,
                 from main.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
using namespace std;
using namespace atcoder;
using mint = modint998244353;
const int inf = 1000000007;
const ll longinf = 1ll << 60;

struct Timer {
    chrono::system_clock::time_point start, last_updated;

    Timer() {
        start = chrono::system_clock::now();
        last_updated = chrono::system_clock::now();
    }

    void reset() {
        start = chrono::system_clock::now();
    }

    void update() {
        last_updated = chrono::system_clock::now();
    }

    double getTime() {
        auto now = chrono::system_clock::now();
        return chrono::duration<double>(now - start).count();
    }
};

Timer timer;
struct Xor128 {
    unsigned x, y, z, w;

    Xor128() : x(123456789), y(362436069), z(521288629), w(88675123){};

    inline unsigned xor128() {
        unsigned t;
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    int nextInt(int x, int y) {
        return xor128() % (y - x) + x;
    }

    double nextDouble(double a, double b) {
        return (double)(xor128() & 0xffff) / 0xffff * (b - a) + a;
    }
};
auto rnd = Xor128();

const int N = 50;
const int mod = 100000000;
int a[N + 1][N + 1];

inline int calc_diff(int x, int y) {
    int diff = abs(x - y);
    return min(diff, mod - diff);
}

void input() {
    int _;
    cin >> _;
    rep(i, N) {
        rep(j, i + 1) cin >> a[i][j];
    }
}

int evaluate(vector<int> &c) {
    vector<vector<int>> ans(N, vector(N, 0));
    rep(i, N) ans[N - 1][i] = c[i];
    for(int i = N - 2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            ans[i][j] = (ans[i + 1][j] + ans[i + 1][j + 1]) % mod;
        }
    }
    int max_diff = 0;
    for(int i = N - 1; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            int diff = abs(ans[i][j] - a[i][j]);
            max_diff = max(max_diff, min(diff, mod - diff));
        }
    }
    return max_diff;
}

void output(vector<int> &c) {
    rep(i, N) cout << c[i] << " \n"[i + 1 == N];
    cerr << evaluate(c) << endl;
}

const int BW = 1050;
const int NS = 10;

struct State {
    int score;
    int nxt_diff;
    vector<int> a;
    State(vector<int> &a, int score) : score(score), a(a), nxt_diff(0) {}
    State(vector<int> &a, int score, int nxt_diff) : score(score), a(a), nxt_diff(nxt_diff) {}
    State() : score(0), a(0), nxt_diff(0) {}
    int evaluate() const {
        if(a.size() == N) {
            return score;
        } else {
            return score + nxt_diff;
        }
    }
    bool operator<(const State &other) const {
        return evaluate() < other.evaluate();
    }
    bool operator>(const State &other) const {
        return evaluate() > other.evaluate();
    }
};

int calc_nxt_diff(vector<int> &v) {
    int m = v.size();
    ll sum = 0;
    rep(i, m) {
        int nxt = (a[m][i] + a[m][i + 1]) % mod;
        sum += calc_diff(nxt, v[i]);
    }
    return sum / m / 1000;
}

vector<State> create_next_row(vector<int> &prv, int diff, int prv_score, int cnt) {
    int m = prv.size();
    int s = 0;
    vector<pair<int, int>> segs;
    rep(i, m + 1) {
        if(i % 2 == 0) {
            // a-diff <=  x + s <= a + diff
            // a - s - diff <= x <= a - s + diff
            int l = a[m][i] - s - diff;
            int r = a[m][i] - s + diff;
            while(l < 0) {
                l += mod;
                r += mod;
            }
            if(r < mod) {
                segs.push_back({l, 1});
                segs.push_back({r + 1, -1});
            } else {
                segs.push_back({l, 1});
                segs.push_back({mod, -1});
                segs.push_back({0, 1});
                segs.push_back({r + 1 - mod, -1});
            }
        } else {
            // a-diff <=  -x + s <= a + diff
            // a - s - diff <= -x <= a - s + diff
            // s - a - diff <= x <= a - s - diff;
            int l = s - a[m][i] - diff;
            int r = s - a[m][i] + diff;
            while(l < 0) {
                l += mod;
                r += mod;
            }
            if(r < mod) {
                segs.push_back({l, 1});
                segs.push_back({r + 1, -1});
            } else {
                segs.push_back({l, 1});
                segs.push_back({mod, -1});
                segs.push_back({0, 1});
                segs.push_back({r + 1 - mod, -1});
            }
        }
        if(i != m) {
            s = (mod + prv[i] - s) % mod;
        }
    }
    sort(segs.begin(), segs.end());
    int c = 0;
    vector<pair<int, int>> valids;
    int len = 0;
    for(auto [v, sgn] : segs) {
        c += sgn;
        if(sgn == 1 && c == m + 1) {
            valids.push_back({v, -1});
            len -= v;
        }
        if(sgn == -1 && c == m) {
            valids.back().second = v;
            len += v;
        }
    }
    if(len == 0) {
        return vector<State>();
    } else {
        cnt = min(cnt, len);
        vector<State> rets;
        rep(_, cnt) {
            int s = 0;
            vector<int> ret(m + 1);
            int target_seg = rnd.nextInt(0, valids.size());
            auto [l, r] = valids[target_seg];
            int target = rnd.nextInt(l, r);
            int score = prv_score;
            rep(i, m + 1) {
                if(i % 2 == 0) {
                    ret[i] = (target + s) % mod;
                } else {
                    ret[i] = (mod - target + s) % mod;
                }
                if(i != m) {
                    s = (mod + prv[i] - s) % mod;
                }
                score = max(score, calc_diff(ret[i], a[m][i]));
            }
            rets.push_back(State(ret, score, calc_nxt_diff(ret)));
        }
        return rets;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    vector<State> states;
    rep(i, BW) {
        vector<int> v = {rnd.nextInt(0, mod)};
        states.push_back(State(v, max(int(4.3e7), calc_diff(v[0], a[0][0]))));
    }
    rep(turn, N - 1) {
        random_shuffle(states.begin(), states.end());
        nth_element(states.begin(), states.begin() + BW, states.end());
        states.resize(BW);
        vector<State> nstates;
        for(auto &state : states) {
            // cerr << state.a[0] + state.a[1] << " ";
            // cerr << state.evaluate() << " ";
            auto nxts = create_next_row(state.a, state.score, state.score, NS);
            if(nxts.size() >= NS) {
                for(auto ns : nxts) {
                    nstates.push_back(ns);
                }
            } else {
                int ng = state.score, ok = 50'000'000;
                while(ok - ng > 1e6) {
                    int mid = (ok + ng) / 2;
                    auto ret = create_next_row(state.a, mid, state.score, NS);
                    if(ret.size() >= NS) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                }
                auto nxts = create_next_row(state.a, ok, state.score, NS);
                for(auto ns : nxts) {
                    nstates.push_back(ns);
                }
            }
        }
        // cerr << endl;
        states.swap(nstates);
        // cerr << endl;
    }
    nth_element(states.begin(), states.begin() + 1, states.end());
    cerr << states[0].score << endl;
    output(states[0].a);
    return 0;
}