Flipping Signs [AtCoder Beginner Contest 125 D]

https://atcoder.jp/contests/abc125/tasks/abc125_d

解説

https://atcoder.jp/contests/abc125/submissions/5169416

ときにはエスパー力も必要であると教えてくれる問題。
（証明の仕方を知らないので、エスパーと表現してるだけだけど）
だいぶ自明っぽいエスパーなので、エスパー初級問題か。
　
と入っても取っ掛かりはある。

• 1を2つに毎回かけるということなので、負の数のパリティは1回の計算によって変化はしない。

この偶奇性をうまく使っていく。
0があった場合は、変化するのだが、この話はまた後で。
　
ここがエスパー部分だと思うのだが、最終的に負の数は1つか0つにすることができる。
しかも、その負の数にする場所も決めることができる。
　
ここまで来たら、場合分け貪欲法で解く。
配列Aの正の数plus, 負の数minus, ゼロの数zeroをカウントする。
負の数mod2が0であれば、全て正の数にできるので、絶対値の総和が答え。
負の数mod2が1であっても、ゼロが1つ以上含まれれば、そこに-1を押し付けられるので、この場合も絶対値の総和が答え。
問題がそれ以外であるが、誰かに-1を押し付ける必要があり、それは、絶対値が最も小さい数である。
なので、絶対値が最も小さい数の絶対値をmiとすると、絶対値の総和からmiを2回引いてやれば答えになる。
2回引くというのは、
絶対値の総和-miでmi以外の絶対値の総和となり、miだけ負の数になるので、-miを足しているということになる。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
 
	int plus = 0, minus = 0, zero = 0;
	rep(i, 0, N) {
		if (0 < A[i]) plus++;
		else if (A[i] < 0) minus++;
		else zero++;
	}
 
	ll ans = 0;
	if (minus % 2 == 0) {
		rep(i, 0, N) ans += abs(A[i]);
	}
	else if (0 < zero) {
		rep(i, 0, N) ans += abs(A[i]);
	}
	else {
		int mi = inf;
		rep(i, 0, N) chmin(mi, abs(A[i]));
		rep(i, 0, N) ans += abs(A[i]);
		ans -= mi * 2;
	}
	cout << ans << endl;
}