yukicoder : No.1867 Partitions and Inversions

手抜き解法。
https://yukicoder.me/problems/no/1867

問題

1～NのPermutation Pが与えられる。
正整数kに対し、以下の問題を考える。

• Pをk個の連続部分列に分割し、それぞれの連続部分内を昇順にソートして、また元通り連結する。その際、Pの転倒数の最小値を答えよ

k=1～Nのそれぞれに対し、上記問題の解を答えよ。

解法

想定解はO(N^2*logN)だが、計算順など定数倍高速化するとO(N^3)でも通る。
以下その手順を説明。

まず以下を求めておく。累積和など使えばO(N^2)で求められる。
f(a,b) := 部分列としてP[a...b)を1つ選んだ場合、P[a...b)により増加する転倒数への寄与、すなわちP[i]＞P[j]かつi＜a≦j＜bである(i,j)の対の数

dp(n,k) := Pの先頭n要素をk個の部分列に分割する場合の転倒数の最小値
とすると、
dp(n,k) = min(dp(m,k-1)+f(m,n+1))
なのでO(N^3)で解ける。
想定解は、O(N^3)回愚直に上記処理を行うのではなく、一部処理を省略することで速くするが、自分も理解しきれてないので割愛。

int N;
int P[3030];
int S[3030][3030];
int sum[3030];

int from[3030];
int to[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
	}
	
	FOR(x,N) {
		ZERO(sum);
		FOR(y,x) sum[P[y]]++;
		FOR(y,N+1) if(y) sum[y]+=sum[y-1];
		int pat=0;
		for(y=x;y<N;y++) {
			pat+=sum[N]-sum[P[y]];
			S[x][y+1]=pat;
		}
	}
	
	FOR(i,N+1) from[i]=1<<30;
	from[0]=0;
	for(i=1;i<=N;i++) {
		FOR(j,N+1) to[j]=1<<30;
		for(j=i-1;j<=N-1;j++) {
			for(x=j+1;x<=N;x++) to[x]=min(to[x],from[j]+S[j][x]);
		}
		cout<<to[N]<<endl;
		swap(from,to);
	}
	
	
}

まとめ

N=3000なのはO(N^3)による解法を避けるためだと思ったんだけどね…。