GCJ2011 Qualification Round D GoroSort

プログラミングコンテストって参加したことなかったけど，基本的に問題の設定はカオスなのね．．．たしかにアリ本も変な設定の問題は多かったけれど．

問題

• Goroには4本の腕があり，N個の異なる要素を持つ整数をソートすることを考える
• まず，2本の腕で配列の要素の一部を抑えた上で，残りの腕で机を殴る
• 殴ったことにより抑えていない要素はランダムに動く
• ソートを完了させるのに机を殴る回数の期待値はいくらか？

プログラム

うーん，ぱっと考えた感じだと方針がわからない．簡単なケースで類推すると結局は自分の位置と数字がずれてる個数になりそうなことはわかるけど，なぜそうなるのかはきちんと頭の中で証明できてないなぁ．一応その方針で書くと次のような感じで書けるけど，すっきりしていないので気持ち悪い．．．うーむ．

import java.io.*;
import java.util.*;

public class Qualifer_04_2011{
	void solve() throws Exception {
		Scanner sc = new Scanner(new FileReader("./input/D-large-practice.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("./output/Q04_2011output2.txt"));

		int T = sc.nextInt();

		for (int testCase=1; testCase <= T; testCase++) {
			int N = sc.nextInt();
			int res = 0;

			for (int i=1; i <= N; i++)
				if (i!=sc.nextInt()) {
					res++;
				}
			pw.println("Case #" + testCase + ": " + res + ".000000");
		}
		pw.flush();
		pw.close();
		sc.close();
	}
	public static void main(String args[]) throws Exception {
		new Qualifer_04_2011().solve();
	}
}