# ARC135-B Sum of Three Terms

##### tags: `構築練習`

## 問題情報

https://atcoder.jp/contests/arc135/tasks/arc135_b

diff: 1239

## 考えたこと

https://atcoder.jp/contests/abc255/tasks/abc255_e に似た問題設定ですね。

最初の $2$ 要素を固定すると、残りの $N + 1$ 要素の値は芋づる式に決まっていくので、美味い $A_1 (= x), A_2 (= y)$ を発見すれば良い。

$A_1 = x$

$A_2 = y$

$x + y + A_3 = S_1\ \to\ A_3 = S_1 - x - y$

$y + A_4 + A_5 = S_2\ \to\ A_4 = S_2 - S_1 + x$

$A_3 + A_4 + A_5 = S_3\ \to\ A_5 = S_3 - S_2 + y$

$A_4 + A_5 + A_6 = S_4\ \to\ A_6 = S_4 - S_3 + S_1 - x - y$

...

と、 $A_3$ 以降の各値は
- 定数 $-x - y$ (1)
- 定数 $+x$ (2)
- 定数 $+y$ (3)

のいずれかで表現できることが手計算で察した。
- しかも、その表現方法は $\pmod{3}$ の周期になっている！

各値が $0$ 以上であれば良いので
- (1)の場合は、 $x + y$ が定数以下でないといけない
- (2)の場合は、 $x$ が定数以上で無いといけない
- (3)の場合は、 $y$ が定数以上で無いといけない

とわかるので、 $N + 3$ 本の $x, y$ に関する不等式が立てられて、 $x, y$ としてありえる範囲を絞り込むことができた。

## 提出コード

void Main() {
    usize N; input(N);
    std::vector<i64> S(N); input(S);
    i64 mx{0LL}, my{0LL}, pxpy{supl};
    
    std::vector<i64> state(N);
    state[0] = S[0];
 
    for (u32 i{} ; i < N ; i++) {
        if (i % 3 == 0) {
            Chmin(pxpy, state[i]);
        }
        else if (i % 3 == 1) {
            Chmax(mx, -state[i]);
        }
        else {
            Chmax(my, -state[i]);
        }
        if (i + 1 < N) state[i + 1] = S[i + 1] -state[i] - (i == 0 ? 0LL : state[i - 1]);
    }
 
    if (mx < 0 or my < 0 or mx + my > pxpy) {
        YesNo(false);
    }
    else {
        std::vector<i64> ans;
        ans.push_back(mx);
        ans.push_back(my);
        for (u32 i{} ; i < N ; i++) {
            ans.push_back(S[i] - ans[ans.size() - 1] - ans[ans.size() - 2]);
        }
        for (auto a : ans) assert(a >= 0);
        YesNo(true);
        out(ans);
    }
 
}

## 反省会

かかった時間: 50分
- 水diffにしては、あまりにもかかりすぎ！！！！！！まぁ仕方ないのかなぁ
- この回はC問題も水diffで超崖ができている。本番だったらレートが下がってたと思われる。

ひたすら手計算で式変形をゴリゴリしたのが時間ロスだったと思う
- Wolfram等を使うべきだった？

不等式の<>の向きとかにかなり混乱した

初手の方針があっていたのはgood
- AGC063とかでも思ったけど、maspy氏のセットは自分とちょっと相性が良いかもしれない。