ABC133 D - Rain Flows into Dams - ツバサの備忘録

解法

$i$ 番目の山に降った雨の量を $M_{i}$ とします。
すると、以下のような式が成り立ちます。
$M_{1}/2 + M_{2}/2 = A_{1}$
$M_{2}/2 + M_{3}/2 = A_{2}$
$\vdots$
$M_{i}/2 + M_{i+1}/2 = A_{i}$
$\vdots$
$M_{N}/2 + M_{1}/2 = A_{N}$
ということで、これらの式をまとめて $M_{1}$ を求めることを考えてみます。
上の式から順番に、式1,2,...Nと名付けると、
式番号が奇数のものはそのまま、偶数のものには両辺に-1をかけてから、全てを足し合わせてあげます。すると、
$(M_{1}/2 + M_{2}/2)-(M_{2}/2 + M_{3}/2)+(M_{1}/2 + M_{2}/2)...-$ $-(M_{N-1}/2 + M_{N}/2) + (M_{N}/2 + M_{1}/2)$
$= A_{1} - A_{2} + A_{3} - ... - A_{N-1} + A_{N}$
となり、左辺をまとめると、
$M_{1} = A_{1} - A_{2} + A_{3} - ... - A_{N-1} + A_{N}$
となります。
よって、結局 $A$ について、正負を反転させつつ足し合わせていくだけで $M_{1}$ を求めることができます。
そのほかの答えについては、最初の式に一つ一つ当てはめていけば良いです。