第二回全国統一プログラミング王決定戦予選 : C - Swaps

これちょっとヒヤヒヤしたまま通しちゃったな。
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

問題

2つの整数列A,Bが与えられる。両数列の長さをNとする。
Aの2要素をswapする、という作業をN-2回以下行い、A[i]≦B[i]を達成できるか。

解法

事前にB[i]が昇順になるよう、(A[i],B[i])の対を並べ替えておこう。
また、AもBも昇順にソート済みの状況でA[i]≦B[i]を達成できないなら、そもそも達成不可である。

AもBもソート済みでA[i]≦B[i]を達成できる場合、残りはそれが(N-2)回以下のswapで良いかという問題が残る。
(N-1)回のswapを許せば、どんな並べ替えも可能である。
逆に(N-1)回のswapが必須となるのは、Aの要素が大きな1個の巡回列になるような入れかえを要する場合である。

以下では、「条件を満たすために1手かけなくてもいい要素」が1個以上あるかを考える。
B[i]が昇順の場合、各A[i]はあるindexより手前に持ってこなければならない。
x=0から順に、どこのA[i]をA[x]とswapしてA[x]≦B[x]に持ってくるか考える。
この際、i=xで問題ない箇所が1回でもあれば条件を満たす。

そうでない場合、(A[i]≦B[x]を満たす)A[i]とA[x]をswapし、次のxの処理に移る。

int N;
int A[101010],ok[101010];
int B[101010];
pair<int,int> P[101010];
set<int> add[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,N) {
		P[i]={B[i],A[i]};
	}
	sort(A,A+N);
	sort(B,B+N);
	FOR(i,N) {
		if(B[i]<A[i]) return _P("No\n");
	}
	sort(P,P+N);
	FOR(i,N) {
		A[i]=P[i].second;
		B[i]=P[i].first;
	}
	FOR(i,N) {
		ok[i]=lower_bound(B,B+N,A[i])-B;
		//cout<<i<<" "<<A[i]<<" "<<B[i]<<" "<<ok[i]<<endl;
		add[ok[i]].insert(i);
	}
	
	set<int> S;
	FOR(i,N-1) {
		FORR(e,add[i]) S.insert(e);
		//cout<<i<<" "<<S.size()<<endl;
		assert(S.size());
		if(S.count(i)) return _P("Yes\n");
		
		x=*S.rbegin();
		S.erase(x);
		swap(A[i],A[x]);
		swap(ok[i],ok[x]);
		add[ok[x]].erase(i);
		add[ok[x]].insert(x);
	}
	cout<<"No"<<endl;
	
}

まとめ

ちょっとヒヤヒヤしたけど通ってよかった。