\(i\) 人目の宇宙人を単に人 \(i\) と書きます。

石を受け取る操作ではなく渡す操作に注目することで、以下のように言い換えても問題の答えは変わらないことがわかります。

人 \(i\) は \(A_i\) 個の石を持っており、\(i\) 年後に成人する。

人 \(i\) は成人したときに人 \(i + 1, i + 2, \ldots, N\) の順に（石を持っていれば）石を \(1\) 個渡す。

最終的に各宇宙人が持っている石の個数はいくつか？

以下では言い換え後の問題を考えます。

長さ \(N\) の数列 \(C\) と長さ \(N + 1\) の数列 \(D\) を用意し、各要素を \(0\) で初期化します。\(C_i\) が人 \(i\) が受け取る石の数の合計になるように計算をすることを目指します。

人 \(i\) が成人後に石を渡す人を人 \(i + 1, i + 2, \ldots, R_i\) とします。ここで、\(j = i + 1, i + 2, \ldots, R_i\) に対して \(C_j\) に \(1\) を加算したいですが、これを愚直に行ってしまうと全体で時間計算量は \(\Theta(N^2)\) になってしまいます。そこで、以下のように imos 法の要領による高速化を行います。\(D\) が \(C\) の差分を取った数列の役割を果たします。

• \(i = 1, 2, \ldots, N\) の順に以下の操作を行う。
  • （\(i > 1\) のとき） \(C_i\) に \(C_{i - 1} + D_i\) の値を代入する。これにより人 \(i\) が成人したときに持っている石の個数がわかり、\(R_i\) の値が定まる。
  • \(D_{i + 1}\) に \(1\)、\(D_{R_i + 1}\) に \(-1\) を加算する。

これらの操作は全体として \(O(N)\) 時間で行えます。

実装例 (0-indexed)

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	vector<int> c(n), d(n + 1);
	rep(i, n) {
		if (i != 0) {
			c[i] = c[i - 1] + d[i];
			a[i] += c[i];
		}
		int cnt = min(n - i - 1, a[i]);
		a[i] -= cnt;
		d[i + 1]++;
		d[min(n, i + cnt + 1)]--;
	}
	rep(i, n) cout << a[i] << " \n"[i == n - 1];
}