ABC 125 D - Flipping Signs

回答時の方針

Submission #12828298 - AtCoder Beginner Contest 125

最初に全探索を考えた $A_{i},A_{i+1}$ の符号を反転する/しない操作を $0 \leq i \leq N$ の範囲で行うと計算量は $2^{N}$ で間に合わない.次に局所的に $A_{i},A_{i+1}$ の反転操作を考えたときに $A_{i} + A_{i+1} \lt 0$ のときに反転が必要だと思った,これをi=0から貪欲に行えばOKかと思ったが入力例2の -4 -8 -11を操作したときに4 -8 11 となり期待する -4 8 11 にならないことに気づいた.この方針でもう少し考えて-11 -8 -4であれば操作が成り立つことに気づき数列Aをソートしてから実行したところACとなった.

入力例2

10 -4 -8 -11 3

↓

-11 -8 -4 3 10

↓

11 8 4 -3 10

-> 30

考察不足でなんとなくACしたが釈然としない感じだった.

正答

上記解答の考察

隣り合う要素の符号を反転する操作を繰り返すことで任意の位置の $A_{i}$ と $A_{j}$ の符号を入れ替えることが可能.この性質から負となる要素の数が偶数の場合は負の要素全てを反転させることができる.奇数の場合は絶対値 $|A_{i}|$ が最小となる負の要素のみが負の要素として残るが,絶対値 $|A_{j}|$ が最小となる正の要素と比較し $|A_{i}| \gt |A_{j}|$ であれば符号を反転させそうでなければ反転させないことで最大値を得る.

動的計画法

こちらのほうが応用範囲が広いのでこちらを考察して実装できていたほうが良かった.

要素 $A_{i+1}$ までの数列について, $A_{i+1}$ を反転させない場合とさせた場合のそれぞれの最大値 $S_{i+1_0}$ と $S_{i+1_1}$ は $A_{i}$ , $S_{i_0}$ , $S_{i_1}$ で表現することができる.

実際に入力例で見ていく.

5
10 -4 -8 -11 3


S2_0 = 6
S2_1 = 14

S3_0 = max(S2_0 - 8, S2_1 + 8)  = max(-2, 22) = 22
S3_1 = max(S2_0 +8, S2_1 - 8) = max(14, 6) = 14

S4_0 =  max(S3_0 - 11, S3_1 + 11) = max(11, 25) = 25
S4_1 =  max(S3_0 + 11, S3_1 - 11) = max(33, 3) = 33

S5_0 =  max(S4_0 + 3, S4_1 - 3) = max(28, 30) = 30

言語化すると $A_{i}$ を反転しない場合の最大値としては2パターン考えられ, $A_{i-1}$ で反転している場合とそうでない場合であり反転していない場合は $A_{i}$ を $S_{i-1_0}$ に足し反転している場合は $-A_{i}$ を $S_{i-1_1}$ を足せばよい. $A_{i}$ を反転する場合も同様に考えられる.