AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginners Contest 125 D – Flipping Signs
最終的にどういう形を取ることが可能なのか、きちんと考察さえできれば実装は難しくない問題。まあ、それを思いつくのが難しいこともあるわけだけど、この問題については、いくつか手元で試してみれば、すぐ思いつけるのではないだろうか。
# AtCoder Beginners Contest 125 D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_d
# tag: 数列 総和 最大値 範囲操作 考察
# 以下、-1 を乗算することを反転と称する。
# 反転している、していないを 1, 0 で表すとする。
# ..00100.. とある地点が反転している時、その隣を
# 操作することで、 ..00010.. や ..01000.. とできる。
# すなわち、どこが反転しているかは自由に動かすことが出来る。
# また、反転そのものは 2 個ずつ行われることも考慮すると、
# 結局の所、好きなところを偶数個反転できる、ということになる。
# 数列全体で負の数が偶数個なら、その全てを反転させればいい。
# 負の数が奇数個のときを考える……と、
# 全数列のうち、数字をどれか一つ負にしてやる必要がある。
# つまり、絶対値が一番小さいものを負にしてやればいい。
def main():
N = int(input())
A = list(map(int, input().split()))
# 絶対値の合計と最小値、負数の個数を求めていく
abs_total = 0
abs_min = 10**18
negative_cnt = 0
for n in A:
if n < 0:
abs_total -= n
negative_cnt += 1
else:
abs_total += n
if abs(n) < abs_min:
abs_min = abs(n)
# 負数が偶数・奇数で分岐
if negative_cnt % 2 == 0:
print(abs_total)
# 絶対値がマイナスに変わるので、2倍してして引く
else:
print(abs_total - 2 * abs_min)
main()
関連
