Posted at

AtCoder ABC125 D - Flipping Signs (400点)


問題概要

問題のリンク

$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$の最大値を求めよ。


制約条件


  • 入力は全て整数である。

  • $2≤N≤10^5$

  • $−10^9≤A_i≤10^9$


考えたこと

整数列の総和を最大化したいので、正の数をできる限り増やし、負の数をできる限り減らしたい。

入力例で実験をしていく。

入力例1の場合

初期状態
-10
5
-4

$i=1$を選ぶ
10
-5
-4

$i=2$を選ぶ
10
5
4

この時配列の総和は $19$ となる。

入力例2の場合

初期状態
10
-4
-8
-11
3

$i=2$を選ぶ
10
4
8
-11
3

$i=4$を選ぶ
10
4
8
11
-3

この時配列の総和は$30$でこれが最大値である。

上記の実験で以下のことが考えられる


  1. 数の選び方が$i$と$i+1$であるから、左から$-1$を乗算していくのがよい。

  2. 1度の操作で正負を変換するのは2つの数であり、かつ$i=N-1$を選ぶことはできないため、負の数が偶数個の場合は全て正の数に変換可能で、奇数個の場合は一つだけ負の数が残る。

2番は以下のような整数列で考えるとわかりやすい。負の数は左から右に移動していく。

初期状態
-10
4
8
11
3

$i=1$を選ぶ
10
-4
8
11
3

$i=2$を選ぶ
10
4
-8
11
3

$i=3$を選ぶ
10
4
8
-11
3

$i=4$を選ぶ
10
4
8
11
-3

さらに以下のようにどの負の数を残すかは選択可能である。

初期状態
-10
4
3
-11
-8

$i=1$を選ぶ
10
-4
3
-11
-8

$i=2$を選ぶ
10
4
-3
-11
-8

$i=4$を選ぶ
10
4
-3
11
8

よって、負の数が偶数個の場合と奇数個の場合で分けて考えるとよい。


解答

#include <bits/stdc++.h>

using namespace std;

int main() {
int n; cin >> n;
vector<int> a(n);
int m = 0;
for(int i = 0; i < n; i ++) {
cin >> a[i];
if(a[i]<0) {
m ++;
a[i] *= -1;
}
}
long long sum;
if(m%2==0) sum = accumulate(a.begin(), a.end(),0LL);
else sum = accumulate(a.begin(), a.end(),0LL) - (*min_element(a.begin(), a.end()) * 2);
cout << sum << endl;
return 0;
}