Boot camp for Beginners hard 015【D – Flipping Signs】をpython解説

Atcoder Problems　という競プロを勉強する上でのコンテンツがあります。URL

今回は、hard100問の内、15問目を解説していきたいと思います。

問題名　【D – Flipping Signs】

問題

入力

N：整数の数
A[i] : Aという数列のi番目の数

考察

今回の問題で重要なのは、マイナスが何回出てくるかです。その理由について話していきます。

問題の特性をつかむ

上記でも書いた通り、今回の問題はマイナスの個数が重要です。具体例を交えながら説明していきます。

問題特性1

離れている2数であっても、その2つのプラス・マイナスを入れ替えることが可能

ex) 
A = [-10, 2,3,5,6,-8]  の時

手順
i == 0について操作をする
tmp_B = [10, -2,3,5,6,-8]

i == 1について操作をする
tmp_B = [10, 2,-3,5,6,-8]

i == 2について操作をする
tmp_B = [10, 2,3,-5,6,-8]

i == 3について操作をする
tmp_B = [10, -2,3,5,-6,-8]

i == 4について操作をする
tmp_B = [10, -2,3,5,6,8]

上記の例が示す通り、たとえ離れている2数であっても、その2つのプラス・マイナスを入れ替えることが可能です。

問題特性2

マイナスにしたほうが良い数は、絶対値が最小の数

隣り合う数字が2つとも負の数の場合は、操作をしたほうが良いです。

ex) 
A = [-1, -2]
B = [1,2]

また、両方とも正の数の場合は、操作をしないほうがよいです。

ex)
A = [1,2]
B = [1,2]

では、片方が負の数でもう片方が正の数の場合はどうでしょうか？
この場合は、絶対値の小さい方が負の数になるようにします。

A = [1, -2]
B = [-1, 2]

上記２つの特性から、

• マイナスの数が偶数個なら、Aに含まれる数をすべて正の数にできるので、
  Bの最大値 = A[i]の絶対値を取った数の合計
• マイナスの数が奇数個なら、Aに含まれる数を1つを除きすべてを正の数にできるので、
  Bの最大値 = A[i]の絶対値を取った数の合計 – (Aに含まれる中で最小値の絶対値 x 2)

となります。

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N = II()
A = LI()

minus_cnt = 0
for i in range(N):
    if A[i] < 0:
        minus_cnt += 1
        A[i] *= -1

        

if minus_cnt % 2 == 0:
    print(sum(A))
else:
    print(sum(A)-min(A)*2)

まとめ

今回は、爆速で解けた。うれしい。

前の問題 014【C – Digits in Multiplication】
次の問題 016【D – Line++】