AtCoder ARC #053 : C - 魔法使い高橋君

Cでだいぶ苦戦してしまった。なぜかレートが爆上がりしたんだけどなんなんだろ。
http://arc053.contest.atcoder.jp/tasks/arc053_c

問題

N個の数字の対(A[i],B[i])がある。
初期状態の値を0から初めて、各対に対しA[i]を足した後B[i]を引く、ということを順次行う。

N個の対を任意に並べ替え可能とするとき、途中経過の最大値を最小化せよ。

解法

まずA[i]足してB[i]引いた後結果的に値が小さくなる、すなわちA[i]≦B[i]であるケースを考える。
一旦A[i]を足す時最大値を更新しないようにするには、A[i]の小さいものが先に来るように並べ替えるとよい。
(各対を適用するたびに現在地は減少するので、大きなA[i]を足しかねない対は後に回した方が良い)

逆にA[i]＞B[i]であるケースを考える。
全部の対を処理し終わった状態から巻き戻す(B[i]足してA[i]引く)事を考える。
すると上記のようにB[i]が小さいものが後(巻き戻すの場合前)に来るのが良い。

まとめると、A[i]≦B[i]となる対についてA[i]昇順に並べ、その後A[i]＞B[i]となる対についてB[i]降順に並べるとよい。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> A,B;
	FOR(i,N) {
		cin>>x>>y;
		if(x<=y) A.push_back({x,y});
		else B.push_back({y,x});
	}
	sort(ALL(A));
	sort(ALL(B));
	reverse(ALL(B));
	
	ll cur=0, ma=0;
	FORR(r,A) {
		cur+=r.first;
		ma=max(ma,cur);
		cur-=r.second;
	}
	FORR(r,B) {
		cur+=r.second;
		ma=max(ma,cur);
		cur-=r.first;
	}
	cout<<ma<<endl;
}

まとめ

シンプルな問題設定でいいね。