AtCoder Beginner Contest 133：D - Rain Flows into Dams

問題
解法
解答

問題

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

解法

各山に降った雨の総和 S は A_1 + A_2 + ... + A_N であり，山 i と i + 1 に降った雨の総和 x_i + x_(i + 1) は A_i * 2 である．よって，山 1 に降った雨の量 x_1 は S - (A_2 + A_4 + ...) になる．x_k = A_(k - 1) * 2 - x_(k - 1) (k >= 2) の漸化式より，全ての x_i を求めることが出来る．O(N)．