1759-Garland

問題（外部リンク）

1759 -- Garland

実装の概要

計算式のみで正確な値を求めるのは困難なので、二分探索を用いて値を絞り込みます。正しい解の条件は「いかなる点においても座標が0以上であること」です。
両端の座標を初期値として漸化式を解くと、i番目の座標はと表すことができます。これが全ての点で0以上となるかについてはある解につきで検証でき、全体としても十分間に合います。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmpArray = br.readLine().split(" ");
		
		int n = Integer.parseInt(tmpArray[0]);
		double a = Double.parseDouble(tmpArray[1]);
		
		System.out.printf("%.2f", solve(n, a));
	}
	
	static boolean check(int n, double a, double b){
		for(int i = 2; i < n; i++){
			double tmp = ((n - i)*a +(i - 1)*b + (n - 1)*i*i - i*n*n + i - n + n*n)/(n - 1);
			if(tmp < 0){
				return false;
			}
		}
		
		return true;
	}
	
	static double solve(int n, double a){
		double lb = 0;
		double ub = 10000000;
		
		for(int i = 0; i < 100 ; i++){
			double mid = (lb+ub)/2;
			
			if(check(n, a, mid)){
				ub = mid;
			}
			else {
				lb = mid;
			}
		}
		
		return Math.round(ub*100)/100.0;
	}
}