Yukicoder077 レンガのピラミッド

問題概要

長いので見て下さい。

yukicoder077

解法

持っている石の数よりも多い石が必要なピラミッドは作ることができない。
また、頂点の高さがtopであるピラミッドをtopピラミッドと呼ぶことにすると、topピラミッドを作れるとき、top-1ピラミッドを作るのは意味がない。
というのは、石が多い場所からゴミあるいは不足している場所に移動させることから、小さいピラミッドを目指してもそこには過剰分の処理が出てしまうからである。
したがって列のある場所をtopにしたいとしたときに必要な移動回数を全探索すれば良い。

[解説を見た後]中心は固定？っぽいのでもっと簡単に解けた…

計算量:$O(N^2)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define ALL(a)  begin((a)),end((a))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N; cin >> N;
        VI a(N * 100, 0);
        FOR(i, 0, N) {
            cin >> a[i];
        }
        N *= 100;
        int sum = accumulate(ALL(a), 0);
        int s = 0, p = -1;
        while (s + p + 2 <= sum) {
            s += p + 2;
            p += 2;
        }
        int top = (p + 1) / 2;
        LL ans = 1e10;
        int t = top * 2 - 1;
        FOR(s, 0, N - t + 1) {//[s,t)に建てるとする
            LL ret = 0;
            FOR(i, 0, s) {
                ret += a[i];
            }
    
            FOR(i, s, s + t) {
                if (a[i] >= min(i + 1 - s, t - i - s)) {
                    ret += a[i] - min(i + 1 - s, t - i - s);
                }
            }
            FOR(i, s + t, N) {
                ret += a[i];
            }
            ans = min(ans, ret);
        }
    
        cout << ans << "\n";
    
        return 0;
    }