AtCoder ARC #073 : E - Ball Coloring

ギリギリ全完。
http://arc073.contest.atcoder.jp/tasks/arc073_c

問題

N個の袋があり、それぞれ２個のボールが入っている。
i番の袋にボールにはX[i],Y[i]の値が書かれている。

各袋のボールを、青と赤で1つずつ塗ったとする。
Rmax,Rmin,Bmax,Bminをそれぞれ赤く塗ったボールの値の最大値/最小値、青く塗ったボールの値の最大値/最小値、とする。
(Rmax-Rmin)*(Bmax-Bmin)の最小値を答えよ。

解法

全ボールの最小値はRminかBminのいずれか、最大値はRmaxかBmaxのどちらかに来る。
最小値のボールが赤く塗られている場合を考え、最大値のボールが赤青それぞれに来るケースを考えよう。

• 最大値のボールが青く塗られている(Bmaxが最大値)場合
  • Rminが小さく、Bmaxが大きいのだから、(Rmax-Rmin)*(Bmax-Bmin)が最小となるためには、Rmaxを小さくし、Bminを大きくすればよい。
  • よって各袋は小さい方の値のボールを赤、大きい方の値のボールを青く塗ればよい。
• 最大値のボールが赤く塗られている(Rmaxが最大値)場合
  • (Rmax-Rmin)は確定している。またすべての値は[Rmin,Rmax]に含まれるため、どのボールを赤く塗ってもRmax,Rminは変わらない。
  • よって、あとは(Bmax-Bmin)を小さくすることを考える。
  • とりあえず各袋大きい方の値のボールを青くしよう。ただ、その結果Bmaxが大きくなりすぎる可能性がある。
  • 青い方の値が大きすぎる袋については、赤青逆にした方がBmaxが下がるかもしれない。
  • これを順次シミュレートして行こう。
  • 青いボールのうち最大値のものを取り、そのボールが入れ替え可能(同じ袋のうち赤いボールの方が値が小さい)なら赤青入れ替える、ということを繰り返す。
  • あとは青いボールの集合をset等で管理し、Bmax-Bminの最小値を更新していけばよい。

int N;
ll X[202020],Y[202020];
pair<ll,ll> P[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll RI=1LL<<30,RA=0;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		RI=min(RI,X[i]);
		RA=max(RA,Y[i]);
		P[i]={X[i],Y[i]};
	}
	sort(P,P+N);
	
	ll ret=1LL<<60;
	ll LA=P[N-1].first,RB=RA;
	FOR(i,N) RB=min(RB,P[i].second);
	ret=min(ret,(LA-RI)*(RA-RB));
	
	set<pair<ll,int>> S;
	S.insert({P[0].second,1000000});
	FOR(i,N) if(i) S.insert({P[i].second,i});
	while(1) {
		ll dif=S.rbegin()->first-S.begin()->first;
		ret=min(ret,(RA-RI)*dif);
		
		auto a=*S.rbegin();
		S.erase(*S.rbegin());
		if(a.second>=1000000) break;
		S.insert({P[a.second].first,1000000});
	}
	
	cout<<ret<<endl;
}

まとめ

シンプルな設定で手ごろな難易度と解法の問題が作れるのはいいね。