[AtCoder] ABC 133 D – Rain Flows into Dams

2019年7月8日

問題

方針

方程式を立てる

\( 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} \) として、後ろから求めていけばよいです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  int N;
  cin >> N;
  ll A[N];
  ll s = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    s += A[i];
  }
  ll x = s;
  for (int i = 0; i < N - 1; i += 2) {
    x -= 2 * A[i];
  }
  vector<ll> v;
  v.push_back(x);
  for (int i = N - 2; i >= 0; i--) {
    x = 2 * A[i] - x;
    v.push_back(x);
  }
  for (int i = N - 1; i >= 0; i--) {
    if (i == 0) cout << v[i] << "\n";
    else cout << v[i] << " ";
  }
  return 0;
}