時々こういうの見る気がする。とりあえず求めたい値を $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;
}

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

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

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

問題概要

制約

考えたこと