yukicoder : No.270 next_permutation (1)

こっちは妙に早解きできた。
http://yukicoder.me/problems/569

問題

1～Nのpermutationである数列xに対し、辞書順でxの次の数列をf(x)とする。
同じ要素数の２つの数列x,yのL1距離d(x,y)とは、対応する要素同士の差の絶対値の総和とする。

1～Nのpermutationである数列A[i]と、N要素の整数列B[i]、正整数Kが与えられる。
とするとき、を求めよ。

解法

後ろからi個目の数字の値がwrap-roundするのは関数fをi!回行う間に1回である。
よって、K回関数fを適用する間、ほとんどは後ろ20個の数字しか変化せず、20個以上の要素が入れ替わるのは高々1回である。

そのため愚直にnext_permutationを実行して、A[i]とA[i+1]で変化が生じた要素に注目してd(A[i],B)とd(A[i+1],B)の差を順次求めていけばよい。
以下のコードでは「直前x番目にあった要素がy要素目(x＜y)に来たなら、最小x番目の要素まではnext_permutationの影響を受けて入れ替わった」と考えて入れ替わった範囲を求めている。

int N,K;
int P[101010];
int B[101010];
int pre[101010];
ll tot,ct;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(K==0) return _P("0\n");
	FOR(i,N) cin>>P[i], pre[P[i]]=i;
	FOR(i,N) cin>>B[i], ct+=abs(P[i]-B[i]);
	
	tot=ct;
	FOR(i,K-1) {
		next_permutation(P,P+N);
		int mi=N-1;
		for(j=mi;j>=mi;j--) {
			mi=min(mi,pre[P[j]]);
			ct += abs(P[j]-B[j])-abs(P[j]-B[pre[P[j]]]);
			pre[P[j]]=j;
		}
		tot += ct;
	}
	cout<<tot<<endl;
}

まとめ

next_permutationが意外と速い、って事実が習得できて良かった。