文系ギャルが0から始める競技プログラミング#22

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#21

・ABC125D

CよりDのほうが簡単情報を得たので解いていきたいと思います！！！

問題文
N個の整数が並んでおり、順にA1,A2,...,ANです。
あなたはこの整数列に対して次の操作を好きなだけ行うことができます。
操作:1≤i≤N−1を満たす整数iを選ぶ。AiとAi+1に−1を乗算する。
操作終了後の整数列をB1,B2,...,BNとします。
B1+B2+...+BNの最大値を求めてください。

制約
入力は全て整数である。
2≤N≤10^5
−10^9≤Ai≤10^9

入力
入力は以下の形式で標準入力から与えられる。
NA1A2...AN

出力
B1+B2+...+BNの最大値を出力せよ。
― D - Flipping Signs

問題を整理します。
選んだところの前後の符号が入れ替わるってことで、
気が済むまで操作をしたら最大値がいくつになるのか？ってことみたいです。

まず条件を2つに分けます！
1.スタート時点でマイナスの数字が偶数個あった場合
2.スタート時点でマイナスの数字が奇数個あった場合

1は、多分うまいことやればマイナスがなくなります。多分。
2は、多分1個残っちゃうはずなので、一番絶対値が小さいやつに押し付けます。
という戦法で行きたいと思います！！！

int A[100000] = {};
int a[100000] = {};
int Count = 0;
for(int i=0;i<N;i++){
       cin >> A[i];
       a[i] = abs(A[i]);
       if(A[i]<=0){
           Count++;
       }
   }

Aというそのまま持ってくる配列と、aという絶対値をしまう配列を用意します。
で、Aがもし0以下だったら(マイナスだったら)カウントします。

long long ans = 0;

答えはすごくでかそうなのでlong longで…(こないだ覚えた)

if(Count%2==0){
       for(int i=0;i<N;i++){
           ans = ans+a[i];
       }
       }else{
           sort(a,a+N);
           for(int i=1;i<N;i++){
               ans = ans + a[i];
       }
           ans = ans - a[0];
   }

ここで1,2の場合分けをします。
カウントが2で割り切れるかどうか！

割り切れるなら、全部絶対値で足し算したのが答え、
割り切れないなら、並べ替えて一番小さいやつだけ足さず、
おまけに最後に引きます！！！！！！！

ansを出力したら優勝です。（さすがにこれは天才）

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
   int N;
   cin >> N;
   
   int A[100000] = {};
   int a[100000] = {};
   int Count = 0;
   for(int i=0;i<N;i++){
       cin >> A[i];
       a[i] = abs(A[i]);
       if(A[i]<=0){
           Count++;
       }
   }
   
   long long ans = 0;
   
   
   if(Count%2==0){
       for(int i=0;i<N;i++){
           ans = ans+a[i];
       }
       }else{
           sort(a,a+N);
           for(int i=1;i<N;i++){
               ans = ans + a[i];
       }
           ans = ans - a[0];
   }
   
   cout << ans << endl;
   return 0;
}

天の声使ってないので、Cよりサクッと解けました…！
まだまだ優勝していきたいと思います！！！

GWが終わってしまう〜〜〜〜〜〜〜〜〜〜

Outro

#23に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。