Decrease (Judge ver.) [AtCoder Regular Contest 079 E]

http://arc079.contest.atcoder.jp/tasks/arc079_c

解法

http://arc079.contest.atcoder.jp/submissions/1470668
十分高速であろうという解法です。

操作をシミュレーションしていくのだが、操作を以下のようにまとめながらやっていく

1. N回使って、全体に-1する
2. 1回使って、最大の数を-Nして、他を+1する

全体に-1する操作で大分回数は稼いでいるが、まだ遅い。
以下、細かい高速化

操作1
最小の数がN以上のときにやる。
最小の数がN-1以下となる分だけ一気に-1してしまうことにする。

操作2
操作1が行えなくて、最大がN以上のときにやる。
最大の数がN-1以下となる分だけ一気に-N,+1をしてしまう。

これでやると高速に処理できる。
なんで？って言われると困る。

typedef long long ll;
#define INF 1LL<<60
ll count(vector<ll> A) {
    int n = A.size();
    ll ans = 0;
    while (1) {
        ll mi = INF, ma = 0;
        rep(i, 0, n) {
            mi = min(mi, A[i]);
            ma = max(ma, A[i]);
        }
 
        if (ma < n) return ans;
 
        if (n <= mi) {
            ll d = mi - n + 1;
            ans += 1LL * d * n;
            rep(i, 0, n) A[i] -= d;
        } else {
            ll d = ma / n;
            ans += d;
            int id = -1;
            rep(i, 0, n) if (A[i] == ma) id = i;
            rep(i, 0, n) {
                if (i == id) A[i] -= d * n;
                else A[i] += d;
            }
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int N; cin >> N;
 
    vector<ll> A;
    rep(i, 0, N) {
        ll x; cin >> x; A.push_back(x);
    }
 
    ll ans = count(A);
    cout << ans << endl;
}