AtCoder Beginner Contest 125

C - GCD on Blackboard

https://atcoder.jp/contests/abc125/tasks/abc125_c
なかなか方針が思いつかなくて焦りました。

方針

を取り除いた、 の最大公約数を とします。求めるものは の中の最大値です。

ですから、以下2つを求めればよいことがわかります。

• 
• 

は から、 は から順に最大公約数を取っていくことで求めることができます。こうすると、
　
と表せるので、全ての を求めてそれらの最大値を出力します。

ソースコード

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    // a, b の最大公約数
    if(a<b) swap(a,b);
    if(a%b==0) return b;
    else return gcd(b, a%b);
}

int main(){
    int N;  cin >> N;
    vector<int> A(N+1,0);
    for(int i=1; i<=N; i++) cin >> A[i];

    vector<int> G(N+1,0), H(N+1,0);
    G[1] = A[1];  H[N] = A[N];
    // G[i] を求める
    for(int i=2; i<=N; i++){
        G[i] = gcd(G[i-1], A[i]);
    }
    // H[i] を求める
    for(int i=N-1; i>=1; i--){
        H[i] = gcd(A[i], H[i+1]);
    }

    int ans = max(G[N-1], H[2]);
    for(int i=2; i<=N-1; i++){
        ans = max(ans, gcd(G[i-1], H[i+1]));
    }
    cout << ans << endl;
}

D - Flipping Signs

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

方針

問題文の操作を行うことによって、負であるような の位置を自由に左右に動かすことが出来る、と考えます。
例えば のとき、 や と、負の値を右に動かすことが出来ます。
そうして負の値の位置を自由に動かし、負の数が2連続で並べばまとめて二つを正の数にすればよいです。

以上のように考えると、 なる の数を C とすると、
(1) C が偶数のとき
全ての負の数を互いに打ち消し合わせることが出来るため、全ての を 0 以上にすることが出来ます。
よって答えは です。

(2) C が奇数のとき
(a) なる が存在しないとき。
1つを除いた、すべての を 0 以上にすることが出来ます。このとき負の値にするものは、 の中で絶対値が最も小さいものにするべきです。そのような を とすると、答えは となります。

(b) なる が存在するとき。
負の値を全て の隣に移動させてくることによって、全ての を 0 以上にすることが出来ます。このような場合も(a)の式はそのまま有効です。

ソースコード

以下では としており、問題文に記載のものとは定義が違います。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int N;  cin >> N;
    vector<ll> A(N,0);
    vector<ll> B(N,0); // A の絶対値を格納する
    ll sum = 0; // A の絶対値の和
    for(int i=0; i<N; i++){
        cin >> A[i];
        B[i] = abs(A[i]);
        sum += B[i];
    }

    int cnt = 0;
    // A[i] < 0 である i の数をかぞえる
    for(int i=0; i<N; i++){
        if(A[i]<0) cnt++;
    }
   
    if(cnt%2==0) cout << sum << endl;
    else{
        sort(B.begin(), B.end()); // A で絶対値が最小のものは B[0] となる
        cout << sum - 2*B[0] << endl;
    }
}