yukicoder : No.1922 Separate and Attach

これは自分で思いつけた。
https://yukicoder.me/problems/no/1922

問題

1～Nの順列が2つ、P,Qが与えられる。
Pに対し、以下の処理を行う。

• いくつか要素を抜き出し、数列Sとする。
• 残った要素からなる数列をTとする。
• PをS+Tで置き換える。

PをQにするには、最低何回の処理が必要か。

解法

P,Qの値を適当に入れ替え、Pをソートする問題と置き換えよう。
R[i] := P中で値iがある位置、すなわちP[R[i]]=iであるような数列
とする。
R[i]＞R[i+1]であるような箇所は、上記処理を行ってiをS側、i+1をT側に入れることで、位置を逆転させなければならない。

そのような箇所の数をmとすると、2^x≧mとなるxの最小値が解となる。

具体的に以下の並べ方を考えると、2^x≧mを達成できる。
f(i) := R[j]＞R[j+1]となるj＜iの数
とする。n回目のステップでは、f(i)の下からn bit目の値が立っている要素をT側に、立っていない要素をS側に回すようにすればよい。
これは明らかにf(N)=m≦2^xを達成できる。

int N,P[101010],Q[101010],R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		P[x]=i;
	}
	FOR(i,N) {
		cin>>y;
		Q[i]=P[y];
	}
	int sum=1;
	for(i=1;i<N;i++) if(Q[i-1]>Q[i]) sum++;
	FOR(i,20) {
		if(1<<i>=sum) {
			cout<<i<<endl;
			return;
		}
	}
}

まとめ

思いついてしまえば実装は軽いけど、考察はちょっと手間取った。