Rain Flows into Dams [AtCoder Beginner Contest 133 D]

https://atcoder.jp/contests/abc133/tasks/abc133_d

解説

https://atcoder.jp/contests/abc133/submissions/6312080

各山にx1, x2, x3, ... 降ったとする。
すると、ダムには(x1+x2)/2=A1のように溜まっていく。
割り算は面倒なので、全部二倍しておこう。
1. x1+x2=2A1,
2. x2+x3=2A2,
3. x3+x4=2A3,
4. x4+x5=2A4,
...

1. - 2.をすると、x1-x3=2A1-2A2
これ+3.とすると、x1+x4=2A1-2A2+2A3
1回引いて1回足すと、3つ先のxの値をx1に足した値が得られる。
これを繰り返すと、
x1+x1=2A1-2A2+2A3-2A4+....+2AN
となるので、
x1=A1-A2+A3-A4+...+AN
である。
あとは、それを使って、ほかの数を特定する。

int N; ll A[101010];
ll X[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];

	X[0] = 0;
	rep(i, 0, N) {
		if (i % 2 == 0) X[0] += A[i];
		else X[0] -= A[i];
	}

	rep(i, 1, N) X[i] = 2 * A[i - 1] - X[i - 1];

	rep(i, 0, N) {
		if (i) printf(" ");
		printf("%lld", X[i]);
	}
	printf("\n");
}