Codeforces #175 Div2. A. Slightly Decreasing Permutations, B. Find Marble

#175はDiv2なので練習だけ。
この回はPermutation祭りの回。
http://codeforces.com/contest/285/problem/A
http://codeforces.com/contest/285/problem/B

A. Slightly Decreasing Permutations

長さNのPermutation Pとは、1～Nを１回ずつ使った整数配列である。
ここで、Permutationの"decreasing coefficient"とは、P_i > P_(i+1)となるiの数と定義する。
長さNが与えられたとき、decreasing coefficientがKとなる整数配列を答える。

最初のK個をN,N-1,N-2,..,N-(K-1)として、残りを1,2,...,N-(K-2)とするだけ。

void solve() {
	int N,K;
	int i,j,k,res=0;
	
	N=GETi();
	K=GETi();
	int L=1;
	int R=N;
	
	FOR(i,N) {
		if(K) {_P("%d ",R--); K--;}
		else _P("%d ",L++);
	}
	_P("\n");
	return;
}

B. Find Marble

N個の不透明なガラスがあり、S番目の中にビー玉がある。
ここで、１回シャッフルを行うと、i番目のガラスがP[i]番目に移動するとという処理を各ガラス一斉に行う。
ビー玉があるS番目のガラスがT番目に行くまでに必要なシャッフルの最小回数を求める。

S番目のガラスをP[S]番目に動かす、という処理を繰り返し、T番目に到達する数を求めればよい。
シャッフルの仕方によってはTに到達不能だが、不能の場合はN回以内にループするのでわかる。
よってこの処理はO(N)で終わる。

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	S=GETi();
	T=GETi();
	FOR(i,N) P[i+1]=GETi();
	
	FOR(i,N) {
		if(S==T) {
			_P("%d\n",i);
			return;
		}
		S=P[S];
	}
	_P("%d\n",-1);
	
	return;
}

まとめ

Bは問題がわかりにくいなぁ…。