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$で表す。
\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になるようにする。
\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が求める解。長い道のりだった。
手順整理
$ $
- 数列$A'=[A_0,A_1,\dots,A_N,A_{N+1}]=[0,A_1,\dots,A_N,0]$を作成
- $A'$の累積和$B'$、$B'$の累積和$C'$を計算
- $\Sigma,A_i≠0$なら不可能で終了
- $\Sigma,B_i'$が$N$の倍数でなければ不可能で終了
- $\Sigma,B_i'=C_{N+1}'$に合わせて$A'$の「変形1」を行う
- 改めて$B'$、$C'$を計算する
- $min(C_i)$に合わせて$A'$の「変形2」を行う
- 改めて$B'$、$C'$を計算する
- $\Sigma,C_i'$が答え。
AC例
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$から差分や累積和を考えるのは、多分そこにも繋がる概念。
黄パフォの問題は時間をかけて考えれば解ける問題もある。時間内には無理だが勉強にはなる。
お付き合いいただき、ありがとうございました。