Codeforces #823 : Div2 F. Almost Sorted

こっちの方がすんなりだな。
https://codeforces.com/contest/1730/problem/F

問題

N要素の順列Pと、正整数Kが与えられる。
N要素の順列Qのうち、i＜jのときP[Q[i]]≦P[Q[j]]+Kを満たすようなもので、転倒数の最小値を求めよ。

解法

Qの先頭から埋めて行くが、Q[i]は最大i+Kの範囲の値を取りうる。
Kは幸い小さいので、Q[i]を埋める際(i+1)～(i+K)の範囲の値がすでに使われているかbitmaskで状態を保持しながらDPで埋めて行けばよい。

int N,K;
int P[5050],R[5050],inv[5050];
int dp[5050][1<<8];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>P[i];
		R[P[i]]=i;
	}
	for(x=1;x<=N;x++) for(y=x+1;y<=N;y++) if(R[y]<R[x]) inv[x]++;
	
	
	FOR(i,5010) FOR(j,256) dp[i][j]=1<<30;
	for(i=1;i<=K+1;i++) {
		int mask=0;
		FOR(j,K) if(i-(j+1)<=0) mask|=1<<j;
		dp[i][mask]=inv[i];
	}
	
	int mask;
	for(i=1;i<=N;i++) for(mask=0;mask<1<<K;mask++) if(dp[i][mask]<1<<30) {
		//cout<<"$"<<i<<" "<<mask<<" "<<dp[i][mask]<<endl;
		// add mi;
		FOR(j,K) if((mask&(1<<j))==0) {
			x=i-(j+1);
			
			int cost=inv[x];
			FOR(k,j) {
				y=i-(k+1);
				if(mask&(1<<k)) {
					if(R[y]<R[x]) cost--;
					if(R[y]>R[x]) cost++;
				}
			}
			if(R[i]<R[x]) cost--;
			if(R[i]>R[x]) cost++;
			//cout<<"#"<<x<<" "<<cost<<endl;
			dp[i][mask|(1<<j)]=min(dp[i][mask|(1<<j)],dp[i][mask]+cost);
		}
		for(j=i+1;j<=min(N,i+K+1);j++) {
			FOR(x,K) if((mask&(1<<x))==0) {
				y=i-(x+1);
				if(y<j-K) break;
			}
			if(x!=K) continue;
			int nm=((mask<<(j-i))|(1<<(j-i-1)))&((1<<K)-1);
			//cout<<i<<":"<<mask<<" "<<j<<":"<<nm<<" "<<dp[i][mask]<<"+"<<inv[j]<<endl;
			dp[j][nm]=min(dp[j][nm],dp[i][mask]+inv[j]);
			
		}
	}
	cout<<dp[N][(1<<K)-1]<<endl;
}

まとめ

Eをやらずに先こっちやればよかったな…。