diverta 2019 Programming Contest 2

C - Successive Subtraction

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_c

方針

index は 0 始まりとします。 はソートしてよいので、以下では とします。また、最後に残る値を とします。

は各 の符合を適当に変えたのちに総和を取ったものだとみなすことが出来ます。
一番都合のよいことを考えると、 なる については全て符号を変え、 なる については全てそのままにして としたいですが、それは無理かもしれません。もし 個の を選んで符号を変えられるのだとすると、 の符合を変えるべき、ということになります。

実は が許される値となります。これは についての数学的帰納法で示すことが出来ます。
まず のときは自明です。
次に の場合にも成立することを仮定すると、 の場合に 回の操作をした時点で、符号を変えた値は 個のどれかになります。このとき、これまで一度も操作の対象とせずに残ってきた を として選び、もう一方の値を とすることで、 が達成できます。逆に、 とすることで、 が達成できるので、示されました。

以上により がわかりましたが、ではどの のときに が最大になるのかを考えたいです。
これは の累積和 を前計算しておくと、 個の符合を変えるときの は と で計算できるので、全ての について を求めてその最大値をとればよいです。このときの を とします。

の符合を変え、残りはそのままにするような操作の仕方は以下のようになります。

1. 、 として操作を行う。この時点で は となる。
2. 、 として操作を行う。この時点で は となる。
3. 、 とすると、 が得られる。

ソースコード

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

int main(){
    int N;  cin >> N;
    vector<int> A(N,0);
    for(int i=0; i<N; i++) cin >> A[i];
    sort(A.begin(), A.end()); // A はソートしておく

    vector<int> S(N,0); // A の累積和
    S[0] = A[0];
    for(int i=1; i<N; i++){
        S[i] = S[i-1] + A[i];
    }
    
    int M = -1e9;  // 最後に残る値の最大値
    int K = 0;     // M が得られるときに符号を変えた A[i] の数 
    for(int k=1; k<=N-1; k++){
        // k 個の A[i] の符合を反転させる場合は
        // M = S[N-1]-S[k-1]*2 となる。 
        if(M < S[N-1]-S[k-1]*2){
            M = S[N-1]-S[k-1]*2;
            K = k;
        }
    }

    cout << M << endl;
    // 操作の 1.
    for(int i=1; i<K; i++){
        cout << A[N-1] << " " << A[i] << endl;
        A[N-1] = A[N-1] - A[i];
    }
    // 操作の 2.
    for(int i=K; i<N-1; i++){
        cout << A[0] << " " << A[i] << endl;
        A[0] = A[0] - A[i];
    }
    // 操作の 3.
    cout << A[N-1] << " " << A[0] << endl;
}