けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 133 D - Rain Flows into Dams (400 点)

時々こういうの見る気がする。とりあえず求めたい値を  x と置いてみる感じ。

問題概要

 N を奇数とする。整数  A_{0}, A_{1}, \dots, A_{N-1} が与えられるので

  •  x_{0} + x_{1} = 2A_{0}
  •  x_{1} + x_{2} = 2A_{1}
  •  x_{2} + x_{3} = 2A_{2}
  • ...
  •  x_{N-1} + x_{0} = 2A_{N-1}

を満たすような  x_{0}, x_{1}, \dots, x_{N-1} を求めよ。

制約

  •  3 \le N \le 10^{5}-1
  •  N は奇数

考えたこと

問題の構造として

 x_{0} を決めると、残りが芋づる式にすべて決まってしまう」

というのがある。例えば

  •  2A = 6, 16, 14, 10, 10

に対して  x_{0} = 0 とすると

  •  x = 0, 6, 10, 4, 6 (6 - 0 = 6、16 - 6 = 10、14 - 10 = 4、10 - 4 = 6)

と決まるのだけど、最後  6 + 0 = 10 とはなっていないので辻褄が合わない。これが辻褄が合うような  x を見つけたい。 x_{0} = x とすると

  •  x_{0} = x
  •  x_{1} = 6-x
  •  x_{2} = 10+x
  •  x_{3} = 4-x
  •  x_{4} = 6+x

という風になる。

  •  x + (6 + x) = 10

を解いて  x = 2 になる。なお  x_{0} = x とおいたときの  x_{N-1} の式は、  N が奇数だと、「 x_{0} = 0 としたときの  x_{N-1} の値」に  x を足したものになる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], A[i] *= 2;

    // x0 = 0 のとき
    long long offset = 0;
    for (int i = 0; i < N; ++i) offset = A[i] - offset;
    long long x = offset / 2;

    // 復元
    long long cur = x;
    for (int i = 0; i < N; ++i) {
        cout << cur << " ";
        cur = A[i] - cur;
    }
    cout << endl;
}