AtCoder Beginner Contest 125 D問題 Flipping Signs pythonの解答例

本稿について

テスト投稿です。
AtCoder Beginner ContestではじめてD問題(Flipping Signs)が解けた記念でqiita初投稿。
（C問題？解けてませんが何か？）

問題

こちら　を参照

$N$個の整数が並んでおり、順に $A_1, A_2, ... , A_N$ です。
あなたはこの整数列に対して次の操作を好きなだけ行うことができます。
操作:$ 1 ≤ i ≤ N − 1$を満たす整数 $i$ を選ぶ。$A_i$ と $A_{i+1}$ に $−1$を乗算する。
操作終了後の整数列を $B_1 ,B_2, ... , B_N$ とします。
$B_1+B_2+...+B_N$の最大値を求めてください。

解答例

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

abstotal = 0
count_minus = 0
abs_A = []
for i in range(N):
    abstotal += abs(A[i])
    abs_A.append(abs(A[i]))
    if A[i] < 0:
        count_minus += 1

ans = abstotal
if count_minus % 2 == 1:
    ans = abstotal - 2 * min(abs_A)

print(ans)

説明

公式の解説にある「かっこいい解法」で解きました。
かんたんな例をいくつか考えると、負の値が偶数個か、奇数個かのみの場合分けになると推測できます。

偶数個の時

• 全ての数を正数に変換可能
  ⇒答え：(全ての数の絶対値の総和)

奇数個の時

• 負数の任意の1つまで減らすことができる
  ⇒答え：(全ての数の絶対値の総和) - 2 * (最小の絶対値)

ほらね

簡単でしょう？

出典