yukicoder : No.2690 A present from B (Hard)

なるほど。
https://yukicoder.me/problems/no/2690

問題

1～N番の番号を持つN人の人が並んでおり、各人がプレゼントを持っている。
数列Aが与えられる。i回目の手順では、A[i]番の人とA[i+1]番の人が手持ちのプレゼントを交換するとする。

1番の人がi番のプレゼントを得るために、Aに要素を任意に追加できるとき、最小何要素追加すればよいか。
i=2～Nそれぞれの場合について求めよ。

解法

まずO(N^2)解を考える。
dp(i) := i番目の人のプレゼントを1番の人が得るために、必要な要素数の最小値
とする。
初期状態でdp(i) = i-1とし、以下を行う。
これをAの逆順に

• swap(dp(A[j]),dp(A[j+1]))
• dp(i)=min(dp(i-1)+1,dp(i+1)+1)として更新

という作業を繰り返すと、dp(i)が解となる。

これをO(N^2)から高速化する際に、問題となるのはdp(i)=min(dp(i-1)+1,dp(i+1)+1)の部分である。
階差数列dp(i+1)-dp(i)を考えると、swapによって変化するのは高々3か所となることに留意すると、O(N)にできる。

int N,M,A[101010];
int D[101010];
set<int> S[3];
int ret[202020];

void change(int p,int d) {
	if(d>1) d=1;
	if(d<-1) d=-1;
	S[D[p]+1].erase(p);
	D[p]=d;
	S[D[p]+1].insert(p);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) {
		D[i]=1;
		S[2].insert(i);
	}
	S[0].insert(N);
	S[1].insert(N);
	S[2].insert(N);
	FOR(i,M) cin>>A[i];
	for(i=M-1;i>=0;i--) {
		x=A[i]-1;
		
		if(D[x]==1) {
			change(x,-1);
			if(x) {
				if(D[x-1]==1) {
					change(x,0);
				}
				else {
					change(x-1,D[x-1]+1);
				}
			}
			if(x+1<N) {
				if(D[x+1]==1) {
					y=min(*S[0].lower_bound(x+1),*S[1].lower_bound(x+1));
					if(y!=N) change(y,D[y]+1);
				}
				else {
					change(x+1,D[x+1]+1);
				}
			}
		}
		else if(D[x]==-1) {
			change(x,1);
			if(x) {
				if(D[x-1]==-1) {
					change(x,0);
				}
				else {
					change(x-1,D[x-1]-1);
				}
			}
			if(x+1<N) {
				if(D[x+1]==-1) {
					y=min(*S[1].lower_bound(x+1),*S[2].lower_bound(x+1));
					if(y!=N) change(y,D[y]-1);
				}
				else {
					change(x+1,D[x+1]-1);
				}
			}
		}
	}
	int mi=0;
	FOR(i,N-1) {
		ret[i+1]=ret[i]+D[i];
		mi=min(mi,ret[i+1]);
	}
	for(i=1;i<N;i++) cout<<ret[i]-mi<<" ";
	cout<<endl;
}

まとめ

色々解き方はありそうだけど、階差を考えるのはシンプルでいいな。