Codeforces #204 Div1. B. Jeff and Furik

さてB。問題文のややこしさに反して、コードは短い問題。
http://codeforces.com/contest/351/problem/B

問題

1～Nのpermutationである数列Pが与えられる。
この数列を以下の手順で昇順にソートしたい。

• 奇数手目は、任意の隣接要素を交換できる。
• 偶数手目は、1/2の確率では、昇順に並んでいる隣接要素のうちランダムに1個交換し、残りの確率で降順に並んでいる隣接要素のうちランダムに1個交換する。

昇順ソートが完了するまでの手数の期待値を答えよ。

解法

隣接要素を交換しないといけない最少回数はバブルソートの交換回数なので、数列中各要素の手前にあるより大きな数の個数の和である。
この必要交換回数をxとする。

奇数手目は、降順になっている箇所を1回交換するので、1手でxを1個減らせる。
偶数手目は、1/2の確率でxが1個減り、1/2の確率でxが1個増える。
合わせると、1/2の確率で2手でxが2個減り、1/2の確率で2手でxが減らない。

よって、x回交換するまでの求める期待値をF(x)とすると、x<2では奇数手目までの手順で終わるのでF(0)=0、F(1)=1。
x>=2ならF(x)=2+(F(x)+F(x-2))/2なので変形してF(x)=F(x-2)+4

ここからxが偶数ならF(x)=2x、奇数ならF(x)=2x-1となる。

int N;
int P[5000];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	j=0;
	FOR(y,N) FOR(x,y) if(P[x]>P[y]) j++;
	double re = j*2-(j%2);
	_P("%.6f\n",re);
	return;
}

まとめ

一見ややこしいけど、シンプルな漸化式になるね。