競プロがんばりたい

Align

精進

Tenka1 Programmer Beginner Contest-C "Align"

めちゃくちゃコード読みにくいので見ないでくださいw

恥ずかしいです

提出コード

考察

作る数列を $\left\{ b_n \right\}$ とします．

このとき，ある $i$ について $b_{i-1} \leq b_i \leq b_{i+1}$ や， $b_{i-1} \geq b_i \geq b_{i+1}$ となるようなものは存在しないことが次のようにわかります．

共に同様に示せるため，前半のみ示します．

この $3$ 項間で差を見てみると，

$(b_i-b_{i-1}) + (b_{i+1}-b_i) = b_{i+1}-b_{i-1}$

となり， $b_i$ は間に挟まっている意味がない，つまり別の位置に $b_i$ を移動させた方がより全体の和を最大化できます．

$b_{i-1} \geq b_i \geq b_{i+1}$ も同様にあり得ません．

以上より，場合分けは次のような $2$ 通りを試す必要があります．

・ $b_0 \leq b_1 \geq b_2 \leq b_3 \geq ....$

・ $b_0 \geq b_1 \leq b_2 \geq b_3 \leq ....$

$N$ が偶数か奇数かによって末尾の状況は違います．

具体例として， $\left\{ b_n \right\} = \left\{ b_0, b_1, b_2, b_3, b_4 \right\}$ を考えます．

$b_0 \leq b_1 \geq b_2 \leq b_3 \geq b_4$ と， $b_0 \geq b_1 \leq b_2 \geq b_3 \leq b_4$ の $2$ パターンで隣接差の和を計算して大きい方が答えです．

・ $b_0 \leq b_1 \geq b_2 \leq b_3 \geq b_4$ のとき

答えは

$(b_1-b_0)+(b_1-b_2)+(b_3-b_2)+(b_3-b_4)$

です．

明らかに，indexが奇数のときは $2$ 倍して足す，indexが偶数のときは $2$ 倍して引く，という操作を繰り返せばOK．

ただし先頭は $1$ 倍して引いて，末尾も $1$ 倍して引きます．(要はそのまま足し引き)

これより，各 $b_i$ は $2$ 倍して足す， $1$ 倍して足す， $1$ 倍して引く， $2$ 倍して引く，のいずれかに分類されます．

(なお， $1$ 倍して足し引きするのは先頭か末尾だけなので実際は $2$ 倍して足し引きがメインです)

最大化したいので， $A[$ ]の大きい数字ほど $2$ 倍したいです．

ということで， $A[$ ]の大きい方から $2$ 倍して足す， $1$ 倍して足す， $1$ 倍して引く， $2$ 倍して引く，と順に和を求めていくことで $O(N)$ で答えが得られます．

$N$ が偶数のときは末尾をそのまま足しますが，違いはそれだけです．

・ $b_0 \geq b_1 \leq b_2 \geq b_3 \leq b_4$ のとき

上の場合分けと同様にできます．

$N$ が偶数か奇数かで先頭と末尾が少しずつ違います．

感想

最初はlistを作って小さい数 $\to$ 大きい数 $\to$ 小さい数...と新しい数列を作っていましたが無事に沼にハマりました．

今回はしっかり解説を見てしまいました．

何ヶ月後かにはスムーズに解きたい．