AtCoder Beginner Contest 133 D - Rain Flows into Dams

問題概要

　奇数個存在する山それぞれに偶数リットルの雨が降り、各山の左右に存在するダムに等しく分散し、 $A_i(L)$ づつ貯まった。各山に対する降水量を求めよ。

解法

　まず、各ダムの水の量は $\frac{(左右の山の降水量の総和)}{2}$ 　　　であるから、当然のことながらどこか1つの山に降った雨の量を定めることができれば他の山に降った雨の量も連鎖的に判明する。

　そこで、0番目の山に降った雨の量を定めてみることを考える。

　 $i$ 番目の山の降水量を $B_i$ とすると、先ほども書いたように、 $B_i+B_{i+1}=2A_i$ という等式が成り立つ。 $B_0=S-B_1-B_2-...B_N$ ( $S$ は降水量の総和( $=A_0+A_1+...A_N$ ))であるから、この式を先ほどの等式を用いて書き換えると、