diverta 2019 Programming Contest 2 C - Successive Subtraction (500)

C - Successive Subtraction

概要

N項の数列Aが与えられる。これらの数列が黒板に書いてある。次の操作を繰り返し行い、最終的に黒板に書いてある数字が1つになった時の数字の最大値と、その数値を与える操作を出力せよ。

• 黒板の数字を2つ選び、x, yとする。x, yを黒板から消去し、かわりにx - yを黒板に書く。

制約

2 ≦ N ≦ 10^5
-1 * 10 ^ 4 ≦ Ai ≦ 10^4

方針

Aが全てマイナス、または全てプラス以外の場合は、Aの絶対値の和が最大値となる。
この場合、具体的な手順は下記の通り。

①Ai < 0 なるAiとAj ≧ 0 なるAjを選び、Ai, Ajを黒板から消去、Ai - Ajを黒板に記入。
②上で書いた数curとAj ≧ 0 を選び、cur, Ajを黒板から消去、cur - Ajを黒板に記入。
これをAj ≧ 0 なるjが残り1つになるまで繰り返す。
③Ai ≧ 0 なるAiとcurを選び、Ai, curを黒板から消去、Ai - curを黒板に記入。
（※Ai ≧ 0 なるAiが1つだけの場合は①～③の手順でなく、下記を行う。
Ai ≧ 0なるAiとAj < 0 なるAjを選び、Ai, Ajを黒板から消去 、Ai - Ajを黒板に記入)
④上で書いた数curとAj < 0なるAjを選び、cur, Ajを黒板から消去、cur - Ajを黒板に記入。
これをAj ≧ 0 なるjがなくなるまで繰り返す。

Aが全てマイナス、または全てプラスの場合は、絶対値が最も小さいものが逆の符号になるような操作を行う。

感想

けんちょんさんのブログを参考にしました。
drken1215.hatenablog.com

実装も工夫されていてわかりやすいです。

解答

Submission #6201161 - diverta 2019 Programming Contest 2

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> A(N);
    rep(i, N) cin >> A[i];
 
    vector<ll> plus, minus;
    rep(i, N){
        if(A[i] >= 0) plus.push_back(A[i]);
        else minus.push_back(A[i]);
    }
 
    sort(plus.begin(), plus.end(), greater<ll>());
    sort(minus.begin(), minus.end());
 
    if(minus.empty()) minus.push_back(plus.back()), plus.pop_back();
    if(plus.empty()) plus.push_back(minus.back()), minus.pop_back();
 
    vector<pll> res;
    ll cur = minus[0];
    for(int i = 0; i+1 < plus.size(); i++){
        res.push_back({cur, plus[i]});
        cur -= plus[i];
    }
 
    res.push_back({plus.back(), cur});
    cur = plus.back() - cur;
 
    for(int i = 1; i < minus.size(); i++){
        res.push_back({cur, minus[i]});
        cur -= minus[i];
    }
 
    cout << cur << endl;
    for(auto p : res) cout << p.first << " " << p.second << endl;
 
}