[AtCoder] ABC 133 D – Rain Flows into Dams

問題

方針

方程式を立てる

\( N = 2n + 1 \) として考えます。

山 \( i \) に降った雨の量を \( x_i \) とします。このとき、

\[
\begin{eqnarray}
\dfrac{x_1}{2}  + \dfrac{x_2}{2} &=& A_1\\
\dfrac{x_2}{2}  + \dfrac{x_3}{2} &=& A_2\\
\dfrac{x_3}{2}  + \dfrac{x_4}{2} &=& A_3\\
&\vdots&\\
\dfrac{x_{2n -1}}{2}  + \dfrac{x_{2n}}{2} &=& A_{2n-1}\\
\dfrac{x_{2n}}{2}  + \dfrac{x_{2n+1}}{2} &=& A_{2n}\\
\dfrac{x_{2n+1 }}{2}  + \dfrac{x_1}{2} &=& A_{2n+1}
\end{eqnarray}
\]

となります。よって、\( S_{2n+1} = A_1 + A_2 + \cdots + A_{2n+1} \), \(X_{2n+1} = x_1 + x_2+ \cdots + x_{2n+1} \) とすると、

\[X_{2n+1} = S_{2n+1}\]

となります。ここで、\( x_{2n+1} = X_{2n+1} – (x_1 + x_2 + \cdots + x_{2n})\) を考えます。また、

\[x_1 + x_2 + \cdots + x_{2n} = 2A_1 + 2A_3 + \cdots + 2A_{2n – 1}\]

となるので、\( x_{2n+1} = S_{2n+1} – (2A_1 + 2A_3 + \cdots + 2A_{2n – 1}) \) となります。

全ての \( x_i \) を求める

上記より、\( x_N \) が求まっています。また、\( x_i + x_{i + 1} = 2A_i \ (1 \leq i \leq N – 1)\) となるので、\( x_{N – 1} = 2A_{N-1} – x_{N} \) として、後ろから求めていけばよいです。

コード