くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

Codeforces #712 Div.2 A. Memory and Crow

要約

数列b_1, b_2, \cdots,b_n が与えられる.
a_i = b_i-b_{i+1}+b_{i+2}-\cdots+b_{n} を満たすような a_i を求めよ

やること

後ろから考えると速い. n が思いの外大きかったのでTLEに気をつけよう

a_i = b_i - \sum_{j=i}^{N} (-1)^{j-i}*a_j

を求めるんだけど, 総和の部分は以下のソースコードのように反転させながら足していかないとTLEする(2敗)

SourceCode

今回からSolve関数のみとなります

void solve() {
	int N = in();
	vector<int> b = in(N);
	vector<int> res(N);

	int add = 0;
	res[N - 1] = b[N - 1];
	add += res[N - 1];

	RFOR(i, 0, N-1) {
		add *= -1;
		res[i] = b[i] - add;
		add += res[i];
	}

	REP(i, N) cout << res[i] << (i == N - 1 ? "\n" : " ");
}