AtCoder ABC #178 : F - Contrast

このやり方は賢いなぁ…。
https://atcoder.jp/contests/abc178/tasks/abc178_f

問題

2つのN要素の整数列A,Bが与えられる。
いずれも昇順に並んでいる。

Bを並べ替え、A[i]==B[i]となるiがないようにせよ。

解法

Editorialの内容が賢かったのでそれを紹介。
AとBである値が(N+1)回以上登場する場合解なし。

C(i) := Aにおけるi以下の値の登場回数
D(i) := Bにおけるi以下の値の登場回数
とする。BをC(i)-D(i-1)回右にrotateすると、Aにおいてiの来ている箇所に、Bの(i-1)以下が来るようになる。
そこでmax(C(i)-D(i-1))だけ右にrotateするとよい。

int N;
int A[202020],B[202020];
int NA[202020],NB[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		NA[A[i]]++;
	}
	FOR(i,N) {
		cin>>B[i];
		NB[B[i]]++;
	}
	
	int ma=0;
	for(i=1;i<=N;i++) {
		if(NA[i]+NB[i]>N) return _P("No\n");
		NA[i]+=NA[i-1];
		NB[i]+=NB[i-1];
		ma=max(ma,NA[i]-NB[i-1]);
	}
	
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<B[(i+N-ma)%N]<<" ";
	cout<<endl;
	
	
}

まとめ

いろいろな解法がありそうね。