ARC129 - D -1+2-1

https://atcoder.jp/contests/arc129/tasks/arc129_d

Cが解けずにABの2完だったが、Dの方が解ける確率が高かったかも？

# -1, +2, -1 ?

$\,-1, 2, -1\,$ という数列は何か引っかかる。
$(x-1)^2$の係数$\,1, -2, 1\,$ に$-1$を掛けたもの。
微分とか、物理とか、場の理論入門とかでも見かけるか。
たとえば位置$x$を時間$t$の関数として$x_t$で表すとする。
同様に速度を$v_t$、加速度を$a_t$で表す。

```math
\begin{align}
v_t &≒ \frac{x_{t+Δt} - x_t}{Δt}\\\\

a_t &≒ \frac{v_{t+Δt} - v_t}{Δt}\\\\
     &≒ (\frac{x_{t+2Δt} - x_{t+Δt}}{Δt} - \frac{x_{t+Δt} - x_t}{Δt}) / Δt\\\\
     &≒ \frac{x_{t+2Δt} - 2x_{t+Δt} + x_t}{Δt^2}\\\\
\end{align}
```

$ $加速度を$x$で表した時の係数に$\,1, -2, 1\,$が現れる。
数列の差分をとるとかで何か見えてきそう。

# 数列の差分をとる

$B_n = A_n - A_{n-1}$ とする。
$A_{i-1}, A_i, A_{i+1}$にそれぞれ$-1,2,-1$を足すと
$B_i\,(=A_i-A_{i-1}),\,B_{i+1}\,(=A_{i+1}-A_i)$ はそれぞれ$\,3, -3$を足したことになる。だが影響はそれだけではない。
$B_{i-1}\,(=A_{i-1}-A_{i-2}),\,B_{i+2}\,(=A_{i+2}-A_{i+1})$ はそれぞれ$\,-1, 1$を足したことになる。
$B_{i-1},\,B_i,\,B_{i+1},\,B_{i+2}$にそれぞれ$\,-1,3,-3, -1$を足す になった。

差分を取ることで、値が変化する項が３つから４つに増えた。筋が悪い。

# 数列の差分をとるの逆をする

逆の操作をするとどうか。逆とは…?

$ $累積和をとること。$B_n = \Sigma_{i=1}^n A_i$ とする。
$A_{i-1}, A_i, A_{i+1}$にそれぞれ$-1,2,-1$を足すと、
$B$は累積和なので$B_{i-1}, B_i, B_{i+1}$にそれぞれ$-1, 1, 0$を足すことになる。$B_{i+1}$は操作していないこと。
$ $つまり、$A_i$を中心とした操作をすることは、$B_{i-1}, B_i$にそれぞれ$-1, 1$を足すことと同値。
値が変化する項が３つから２つに減った。筋がよい。

$C_n = \Sigma_{i=1}^n B_i$ とする。
$B_{i-1}, B_i$にそれぞれ$-1, 1$を足すと、$C_{i-1}, C_i$にそれぞれ$-1, 0$を足すことになる。$C_i$は操作していないことと同じことになる。
$ $つまり、$A_i$を中心とした操作をすることは、$B_{i-1}, B_i$にそれぞれ$-1, 1$を足すことと同値で、$C_{i-1}$に$-1$を足すことと同値。

$ $ということは、数列全体に対して計$n$回操作すると、数列$C$の総和が$n$減少する。
つまり、必要な操作回数は最初の$\Sigma_{i=1}^n C_i$であるということになる。

$ $ただし、**操作が循環していなければ**の話。$A_1$や$A_N$を中心とする操作が考慮されていない。
結局ここから2時間くらいかかったので、本番中も解けなかったであろう。

# 循環から非循環に

$ $累積和を利用しているので、循環する数列は扱いにくい。
問題となるのは数列の端で操作するとき。つまり、$A_N, A_1, A_2$ のときと $A_{N-1}, A_N, A_1$を操作するとき。

$A_0, A_{N+1}$を創設し、そこから“-1”されるようにする。
$ $新しい数列を$A'=[A_0',A_1',\dots,A_N',A_{N+1}']$とする。

$A_0'$は$A_1'$を中心とする操作で-1されるための、$A_N$の代わり。$A_0'+A_N'=A_N\, $。
$A_{N+1}'$は$A_N'$を中心とする操作で-1されるための、$A_1$の代わり。$A_1'+A_{N+1}'=A_1\, $。

$ $創設された項目は+2される対象にはしない。+2するときは元々の$A_1'$と$A_N'$で行う。

$ $たとえばサンプル1$\,(A=[3,0,-1,-2])\,$のとき。
結果的に$\,A_4\,(=-2)$を中心とする操作が2回行われている。これに伴い、$A_1$から2回-1されている。
$A_1\,(=3)$のうち、$A_4$を中心とする操作で変化する成分$(2)$を$A_5$として$A_4$の右側に置く。
$B_k'=\Sigma_{i=0}^k\,A_i'$ , $C_k'=\Sigma_{i=0}^k\,B_i'$。

$A' = [0, 1, 0, -1, -2, 2]\quad$($\,A=[3,0,-1,2]$から変換)
$B' = [0, 1, 1,  0, -2, 0]$
$C' = [0, 1, 2,  2,  0, 0]$
$\Sigma\,C'_i = 5$

合っている。

# 可能かどうかの条件

$A$のすべての要素を$0$にすることが可能かどうかの条件。
$A'$のすべての要素を$0$にすることができれば十分。
$A'$については、$\Sigma\,A_i'$は操作で増減しないので、初めから$0$であることが必要。これは$A_0'$や$A_{N+1}'$のとり方によらない。
$B'$については、$A_i'$を中心とする操作で$\Sigma\,B_i'=0$は変化しないので、これも初めから$0$であることが必要。これは$A_0'$や$A_{N+1}'$のとり方で変わってくる。
$C'$については、操作ごとにいずれかの要素が-1されるので、負の数の要素があると不可能。各$C_i'$の値も$A_0'$や$A_{N+1}'$のとり方で変わってくる。

まとめると

$ $**条件1**：$\Sigma\,A_i ≡ \Sigma\,A_i = 0$ である
$ $**条件2**：$A_0'$と$A_{N+1}'$をうまくとることで$\Sigma\,B_i'=0$とすることができる
$ $**条件3**：$A_0'$と$A_{N+1}'$をうまくとることで全ての$i$において$C_i≥0$とすることができる

# 「うまくとる」ための考察

$A_0'$と$A_{N+1}'$をうまくとる。どうする？まずは値の範囲を考える。
“-1”されるための対象なので、下限は0。上限はわからない。
$ $上限が100くらいでよければ、総当たりもちょっと考えるが、$A_0'$と$A_{N+1}'$のとりかたがそれぞれ100通りくらいなので$O(100^2*N) = O(10^9)$で無理そう。
$A_0'$や$A_{N+1}'$を少し変化させた場合の$B'$や$C'$の変化を観察する。

$ $1. $A_0'$を+1したとき。
$A_N'$からとってくるので$A_N'$は-1される。

```
 i :  0  1  2 ... N-1  N  N+1  Δ総和
ΔA': +1  0  0 ...  0  -1   0    ±0
ΔB': +1 +1 +1 ... +1   0   0    +N
ΔC': +1 +2 +3 ... +N   N   N    +N(N+1)/2+2N
``` 

$ $2. $A_{N+1}'$を+1したとき。
$A_1'$からとってくるので$A_1'$は-1される。

```
 i:  0  1  2 ...   N-1   N  N+1  Δ総和
ΔA:  0 -1  0 ...    0    0  +1    ±0
ΔB:  0 -1 -1 ...   -1   -1   0    -N
ΔC:  0 -1 -2 ... -(N-1) -N  -N    -N(N+1)/2-N
``` 

$A_0'$を$x$回 +1し、$A_{N+1}'$を$y$回 +1したとき$A_0=x,A_{N+1}=y$であり、変化量は以下のようになる。

```
 i :  0   1    2   ...   N-1         N      N+1          Δ総和
ΔA': +x   -y   0   ...    0         -x       +y           ±0
ΔB': +x  x-y  x-y  ...  x-y         -y        0         N(x-y)
ΔC':  x 2x-y 3x-2y ... Nx-(N-1)y  N(x-y)  N(x-y)  (x-y)N(N+1)/2+(2x-y)N
```  

$C$の総和のあたりがおかしいことになっているが、できる範囲で進める。

$ $条件1：$\Sigma\,A_i = \Sigma\,A_i' =0$で満たされている。
$ $条件2：$\Sigma\,B_i' =0$を満たすには、$\Sigma\,B_i$が$N$の倍数であることが必要条件。そうでなければ、不可能。
$ $条件3：$C_i'≧0$を全ての$i$で満たす方法は、ちょっとわからない。

$x-y=k$とおいてみる。$y=x-k$。

```
 i:  0   1    2  ...   N-1      N    N+1          Δ総和
ΔA: +x -x+k    0 ...    0       -x   x-k           ±0
ΔB: +x    k    k ...    k     -x+k     0           Nk
ΔC:  x  x+k x+2k ... x+(N-1)k   Nk    Nk   kN(N+1)/2+(x+k)N
```  

$C_i'$についてはまだ見通しが悪い。

# 段階的に進める

$ $とりあえず、$\Sigma\,B_i' =0$を満たすようにする。$\Sigma\,B_i + N(x-y) = \Sigma\,B_i' = 0$となるように$x$、$y$をとる。
まずはなるべくシンプルに、$x$か$y$のいずれか一方は0になるようにする。

```math
\begin{align}
&x = -\frac{\Sigma\,B_i}{N},\quad y=0\quad(\Sigma\,B_i'<0)\\
&x = 0,\quad y = \frac{\Sigma\,B_i}{N}\quad(\Sigma\,B_i'>0)
\end{align}
```

$ $ここで得られた$x$、$y$で$A_0'=x$,$\quad A_{N+1}'=y$となるように$A'$をつくる。（「変形1」と呼ぶ）
$(\;A'=[x,A_1-y,A_2,\dots,A_{N-1},A_N-x,y]\;)$

サンプル4に適用してみる。

```
---- sample 4 ----
input:
     1 | 10
     2 | -28 -3 90 -90 77 49 -31 48 -28 -84

your output:
     変形1の前。
     1 | A'_0 = 0, A'_N+1 = 0
     2 | A': [0, -28,  -3, 90, -90, 77,  49, -31,  48, -28, -84,   0] sum:    0
     3 | B': [0, -28, -31, 59, -31, 46,  95,  64, 112,  84,   0,   0] sum:  370
     4 | C': [0, -28, -59,  0, -31, 15, 110, 174, 286, 370, 370, 370] sum: 1577
     Bの総和は 370 > 0 なので、x = 0, y = 370/10 = 37

     変形1の後。
     5 | A'_0 = 0, A'_N+1 = 37
     6 | A': [0, -65,   -3,  90,   -90,   77,   49, -31,  48, -28, -84, 37] sum:    0
     7 | B': [0, -65,  -68,  22,   -68,    9,   58,  27,  75,  47, -37,  0] sum:    0
     8 | C': [0, -65, -133, -111, -179, -170, -112, -85, -10,  37,   0,  0] sum: -828
```

$\Sigma\,B_i'=0$になった。あとは$C_i'≧0$になってくれれば。

# 最終調整

$ $変形1で$\Sigma\,B_i'=0$になった。あとはこれを保ったまま$x$、$y$を変化させる。
$\Sigma\,B_i = \Sigma\,B_i + N(x-y)'\;$だから$x$と$y$を同時に1ずつ増やせばよい。(「変形2」と呼ぶ)
変化表は以下の通り。

```
 i:  0  1  2 ... N-1  N  N+1  Δ総和
ΔA: +1 -1  0 ...  0  -1  +1    ±0
ΔB: +1  0  0 ...  0  -1   0    ±0
ΔC: +1 +1 +1 ... +1   0   0     N
``` 

$ $つまり、$C_0,C_1,\dots,C_{N-1}$の中で最も小さい負の数に合わせて$x$も$y$も増やせばよい。
前掲のサンプル4。「変形1」($A_0' = 0→0, A_{N+1}'=0→37$)の後。

```
     5 | A'_0 = 0, A'_N+1 = 37
     6 | A': [0, -65,   -3,  90,   -90,   77,   49, -31,  48, -28, -84, 37] sum:    0
     7 | B': [0, -65,  -68,  22,   -68,    9,   58,  27,  75,  47, -37,  0] sum:    0
     8 | C': [0, -65, -133, -111, -179, -170, -112, -85, -10,  37,   0,  0] sum: -828
     C'_iの最低値はC'_4 = -179なので、変形2を179回適用する。

     9 | A'_0 = 179, A_N+1 = 216)
    10 | A': [179, -244,  -3, 90, -90, 77, 49, -31,  48, -28, -263, 216] sum:   0
    11 | B': [179,  -65, -68, 22, -68,  9, 58,  27,  75,  47, -216,   0] sum:   0
    12 | C': [179,  114,  46, 68,   0,  9, 67,  94, 169, 216,    0,   0] sum: 962
```

$C'$の総和962が求める解。長い道のりだった。

# 手順整理
$ $
1. 数列$A'=[A_0,A_1,\dots,A_N,A_{N+1}]=[0,A_1,\dots,A_N,0]$を作成
2. $A'$の累積和$B'$、$B'$の累積和$C'$を計算
3. $\Sigma\,A_i≠0$なら不可能で終了
4. $\Sigma\,B_i'$が$N$の倍数でなければ不可能で終了
5. $\Sigma\,B_i'=C_{N+1}'$に合わせて$A'$の「変形1」を行う
6. 改めて$B'$、$C'$を計算する
7. $min(C_i)$に合わせて$A'$の「変形2」を行う
8. 改めて$B'$、$C'$を計算する
9. $\Sigma\,C_i'$が答え。

# AC例

```rust:arc129_d.rs
use proconio::input;

fn main() {
    input!{
        n: usize,
        a: [i64; n],
    }

    // A_0とA_N+1を指定し、A,B,Cの累積和とCの最小値を計算するクロージャ
    let cl = |a0, anp1| {
        let mut a_ = vec![0; n+2];
        for i in 0..n { a_[i+1] = a[i]; }
        a_[0]  =   a0; a_[n]  -=   a0;
        a_[1] -= anp1; a_[n+1] = anp1;
        let mut asum = 0;
        let mut b_ = vec![0; n+2];
        let mut bsum = 0;
        let mut c_ = vec![0; n+2];
        let mut csum = 0;
        for i in 0..n+2 {
            if i > 0 {
                b_[i] = b_[i-1] + a_[i];
                c_[i] = c_[i-1] + b_[i];
            } else {
                b_[i] = a_[i];
                c_[i] = b_[i];
            }
            asum += a_[i];
            bsum += b_[i];
            csum += c_[i];
        }
        let cmin = *c_.iter().min().unwrap();
        (asum, bsum, csum, cmin)
    };

    let ans;
    let n = n as i64;

    let (asum, bsum, _csum, _cmin) = cl(0, 0);
    if asum != 0 || bsum % n != 0 { // 条件1、条件2 を満たさないとき
        ans = -1;
    } else {
        // 変形1
        let k1 = (bsum / n).abs();
        let mut a0 = 0;
        let mut anp1 = 0;
        if bsum >= 0 {
            anp1 = k1;
        } else {
            a0 = k1;
        }
        // 変形2
        let k2;
        let (_asum, _bsum, _csum, cmin) = cl(a0, anp1);
        if cmin < 0 { k2 = -cmin; } else { k2 = 0; }
        a0 += k2; anp1 += k2;
        ans = cl(a0, anp1).2; // Cの累積和をansに割当
    }

    println!("{}", ans);
}
```

典型90問の最終問題でk次漸化式がとりあげられていた。
$-1,2,-1$から差分や累積和を考えるのは、多分そこにも繋がる概念。
黄パフォの問題は時間をかけて考えれば解ける問題もある。時間内には無理だが勉強にはなる。

お付き合いいただき、ありがとうございました。