diverta 2019 Programming Contest 2 : C - Successive Subtraction

前回AGCで赤から落ちたけどここで踏ん張って復帰。
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_c

問題

整数の集合が与えられる。　
任意の2要素を抜き出し、片方から片方を引いて、集合に戻す、という作業を繰り返す。
集合の要素数が1つになったとき、値の最大値と、それを達成する手順を求めよ。

解法

最終的に各要素は最後の値に足すか引くかされた状態になる。
その際、最低1つは足された状態で、1つは引かれた状態でなければならない。

よって最大値を得るには以下のようにするのが最適である。

• もともと非負の要素は、最終的に最後の値に足された状態にする
• もともと負の要素は、最終的に最後の値に引かれた状態にする

ただし、もしすべての要素がどちらかに偏ってしまった場合、前者なら最小値を引き、後者なら最大値を足すことにしよう。
さて、手順の作成だが、最終的に足された状態にする値の集合をP、引かれた状態にする値の集合をMとすると、

• Pが残り1個になるまで以下を繰り返す
  • Pから値pを抜き、Mから値mを抜いて、Mにm-pを戻す。
• その後、Mが空になるまで以下を繰り返す
  • Pから値pを抜き、Mから値mを抜いて、Pにp-mを戻す。

int N;
int A[101010];
pair<int,int> P[101010];
int mi[101010];
vector<pair<int,int>> D;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i]={A[i],i};
	}
	sort(P,P+N);
	int C[2]={};
	FOR(i,N) {
		if(P[i].first<0) mi[P[i].second]=1;
		C[mi[P[i].second]]++;
	}
	
	if(C[0]==N) {
		mi[P[0].second]=1;
	}
	if(C[1]==N) {
		mi[P[N-1].second]=0;
	}
	multiset<ll> S[2];
	FOR(i,N) S[mi[i]].insert(A[i]);
	
	vector<pair<ll,ll>> V;
	while(S[0].size()>1) {
		auto it=S[0].begin();
		auto it2=S[1].begin();
		ll a=*it;
		ll b=*it2;
		S[0].erase(it);
		S[1].erase(it2);
		V.push_back({b,a});
		S[1].insert(b-a);
	}
	while(S[1].size()) {
		auto it=S[0].begin();
		auto it2=S[1].begin();
		ll a=*it;
		ll b=*it2;
		S[0].erase(it);
		S[1].erase(it2);
		V.push_back({a,b});
		S[0].insert(a-b);
	}
	
	cout<<*S[0].begin()<<endl;
	FORR(d,V) cout<<d.first<<" "<<d.second<<endl;
	
}

まとめ

multisetとか無駄に使っちゃったけど、これvectorで十分だったな。