けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

diverta 2019_2 C - Successive Subtraction (水色, 500 点)

復元つらい

問題へのリンク

問題概要

黒板に  N 個の整数  A_1, A_2, \dots, A_N が書かれている。

  • 書かれている数字から 2 個選んで  x, y として、これらを消して  x-y を新たに書き加える

という操作を  N-1 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( x, y を毎ターンごとに出力)

制約

  •  2 \le N \le 10^{5}

考えたこと

この手の問題では、最終的に出来上がりうるものをわかりやすく特徴づけられないか、わかりやすく言い換えられないかを考えることが肝要だと思う。500 点だろうと 700 点だろうと 900 点だろうと。

で、少し考えてみると、例えば元の整数が (2, -4, 5, 6) とかだったとき、最終的に

  • 2 - (-4) + 5 + 6 = 17

とかは作ることができることがわかる。ちょっと手を動かすと

  • ±  A_1 ±  A_2 ± ... ±  A_N の形しか作れない
  • プラスマイナスのうち、「全部がプラス」と「全部がマイナス」は作れない

ということが見えてくる。でもプラスとマイナスが両方とも存在していたら、それは絶対に作れそうだ。復元が要求されていなくて最大値を求めるだけだったら、ここで「証明のない貪欲」を投げる手もあるが、今回は復元もしなければならない。

...とその前に

最大値

上記の仮説を信じて、先に最大値を求めてみる。

もし「全部プラス」や「全部マイナス」が許されているなら単純に、

  •  A_i が正のものはプラス
  •  A_i が負のものはマイナス

とすればよい。でも単純にこれだと「全部プラス」になる場合もあるので、その場合は  A_i が一番小さいところにマイナスをつければよい。「全部マイナス」になる場合については  A_i が一番大きいところにプラスをつければよい。

復元

以上から、各  A_i についてプラスをつけたいのかマイナスをつけたいのかまではハッキリとした。そうなるように操作を復元したい。まずはプラスとマイナスに分類する。

  • プラス: a, b, c, d
  • マイナス: x, y, z

とかになったとする。うまいことやりたい。とりあえず

  • プラス: a, b, c, d
  • マイナス: x

という具合にマイナスが 1 個だけの場合が作れたら、あとはそこから y, z, ... を引き続けるだけになる。これは次のように作れる。

  • x - a
  • x - a - b
  • x - a - b - c
  • d - (x - a - b - c) = (a + b + c + d) - x

という感じ。最後以外は x から引いていって、最後だけ逆から引く感じ。

(一応) 全部プラスと全部マイナスがダメな理由

全部プラスや全部マイナスがダメなのは最初に  N 個の整数の中から  x, y を選んで  x-y としたとき、この部分については、その後の操作で  x-y -x+y かをずっと行き来することになるため。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<long long> A;

void solve() {
    vector<long long> plus, minus;
    for (int i = 0; i < N; ++i) {
        if (A[i] >= 0) plus.push_back(A[i]);
        else minus.push_back(A[i]);
    }
    sort(plus.begin(), plus.end(), greater<long long>());
    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<pair<long long, long long> > res;
    long long 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;
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    solve();
}