TopCoder SRM 667 Div1 Medium: CatsOnTheCircle

解法

mayokoex.hatenablog.com

コード

public class CatsOnTheCircle {

	public double getProb(int N, int K, int p) {
		if (p == 1e9 / 2) { return 1.0 / (N - 1); }
		if (p > 1e9 / 2) {
			K = N - K;
			p = (int) 1e9 - p;
		}

		double pd = p / 1e9;
		return turnRight(N - K - 1, K - 1, pd) * (1 - turnRight(N - 2, 1, pd))
				+ (1 - turnRight(N - K - 1, K - 1, pd))
				* turnRight(1, N - 2, pd);
	}

	private double turnRight(int L, int R, double p) {
		double q = p / (1 - p);
		double r = 1.0 / (1.0 - Math.pow(q, L + R));
		return r * Math.pow(q, R) + 1.0 - r;
	}

}