2011年 冬合宿4日目 Problem C : Fair Game [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;
import static java.lang.Math.*;
import static java.lang.Integer.*;

public class Main {
  public static void main(String... args) {
		new Main().run();
	}

	int n;
	double w;
	double[] c;

	static final double EPS = 1e-9;
	static final double INF = 1e20;
	static final int REP = 35;

	public void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		w = sc.nextDouble();
		c = new double[n];
		for (int i = 0; i < n; i++)
			c[i] = sc.nextDouble();

		double bd = max(PI, w * log(5.));
		double lo = -bd, up = bd;
		for (int i = 0; i < REP; i++) {
			double x = avg(lo, up);
			double s = calc(x) + handicap(x);
			if (s > 0)
				lo = x;
			else
				up = x;
		}
		System.out.println(avg(lo, up));
	}

	double calc(double x) {
		double[] p = new double[1 << n];
		for (int i = 1; i < 1 << n; i++) {
			int t = n - bitCount(i) + 1;
			p[i] = t % 2 == 1 ? -INF : INF;
		}
		for (int i = 1; i < 1 << n; i++) {
			int t = n - bitCount(i) + 1;
			if (t % 2 == 1) {
				for (int j = 0; j < n; j++)
					if ((i & (1 << j)) > 0)
						p[i] = max(p[i], p[i ^ (1 << j)] + score(j, x, t));
			} else {
				for (int j = 0; j < n; j++)
					if ((i & (1 << j)) > 0)
						p[i] = min(p[i], p[i ^ (1 << j)] - score(j, x, t));
			}
		}
		return p[(1 << n) - 1];
	}


	double score(int i, double x, double t) {
		return sin(x + t + c[i]);
	}

	double handicap(double x) {
		return (2 / (1 + exp(x / w)) - 1) * n;
	}

	double avg(double x, double y) {
		return .5 * (x + y);
	}
}