yukicoder : No.1888 Odd Insertion

これは考察が難しい。
https://yukicoder.me/problems/no/1888

問題

S={1,2,....,N}があったとする。
以下の手続きをSが空になるまで繰り返し、数列Aを構成する。

• Sのうち、1番か2番目に小さい整数xをSから取り出す
• Aのうち先頭からy(奇数)番目の位置にxを挿入する

1～Nの順列Pが与えられる。
上記手順でPを構築できるか、可能なら手順を答えよ。

解法

上記x,yをN個並べた数列をX,Yとする。
また、Pの逆置換をQとする。

yの奇数に関する条件と、xで2番目に小さい整数を取り出す手順を無視すると、Xは昇順になる。
また、Y[i]=(Q[1...(i-1)]のうちQ[i]より小さいもの+1)となる。

ここから、Yの条件をそろえていく。
Y[i]とY[i+1]を比較する、という手順をiを小さい順に処理して行く。

もしY[i]が偶数なら、Y[i+1]とY[i]とswapしよう。
これは、xを選ぶとき2番目に小さいものを先取り出すことで、1番小さい値を取るタイミングを1つ遅らせることに相当する。
ただし、Y[i]もY[i+1]も偶数の場合はswapしても条件を満たせないので不可となる。

あとはそれに合わせてX[i]やQ[i]も調整していく。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

int N,P[202020],Q[202020];
int X[202020],Y[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		Q[P[i]]=i;
	}
	
	FOR(i,N-1) {
		int y1=bt(Q[i]);
		int y2=bt(Q[i+1]);
		if(y1%2&&y2%2) {
			cout<<"No"<<endl;
			return;
		}
		if(y2%2==0) {
			if(y1%2||Q[i]<Q[i+1]) {
				swap(Q[i],Q[i+1]);
				swap(y1,y2);
			}
		}
		X[i]=P[Q[i]];
		Y[i]=y1;
		bt.add(Q[i],1);
	}
	X[N-1]=P[Q[N-1]];
	Y[N-1]=bt(Q[N-1]);
	if(Y[N-1]%2) {
		cout<<"No"<<endl;
		return;
	}
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<X[i]+1<<" "<<Y[i]+1<<endl;
}

まとめ

JOI系とかにありそう。