kmjp's blog

競技プログラミング参加記です

Codeforces #309 Div1 B. Kyoya and Permutation

問題文が無駄にややこしい。
http://codeforces.com/contest/553/problem/B

問題

1~Nのpermutationである数列Pを考える。
Pは、1または複数の巡回列から構成されると考えられる。
この巡回列を取り出し、個々の巡回列の構成要素を降順にソートしなおしたうえで、巡回列を昇順に連結してできる数列を考える。

上記処理により並べ替えた数列が、元の数列と一致する場合がある。
Pのpermutationのうち、そのような物を辞書順に並べた場合K個目に来るものを求めよ。

解法

条件を満たすのは、個々の巡回列の長さが1か2の場合である。
仮に降順にしたのちの巡回列が3要素以上で(x...y)と表現できた場合、元の行列はxとyが巡回列を成さなければならないので、(x....y)という巡回列は生成されない。

よって、結局求めたいのは1~Nからなる数列に対し、何か所か隣接項を入れ替えてできる数列のうち、辞書順K番目のものである。

長さaの数列のうち、隣接項を入れ替えてできる数列の数F(a)はDPの容量で考えるとF(a)=F(a-1)+F(a-2)とフィボナッチ数列の関係を成すことがわかる。
この事実をもとに、数列の要素を先頭から入れ替えを行う・行わないを選択してK番目を求めればよい。

ll N,K;
ll fib[60];
int p[55];
int ret[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fib[0]=fib[1]=1;
	for(i=2;i<=50;i++) fib[i]=fib[i-1]+fib[i-2];
	
	cin>>N>>K;
	K--;
	
	FOR(i,N) p[i]=i+1;
	FOR(i,N-1) if(K>=fib[N-i-1]) {
		K-=fib[N-i-1];
		swap(p[i],p[i+1]);
		i++;
	}
	
	FOR(i,N) _P("%d ",p[i]);
	_P("\n");
}

問題

巡回列云々は無駄にややこしいので、隣接2要素を交換して作れる数列…としては行けなかったのかなぁ。
もちろん3要素以上の巡回列を含められないのを考察するのも問題の一部だけどさ。