TopCoder SRM 440

1. 250 Passed System Test 175.27
2. 500 Opened
3. 1000 Opened

250をもうちょっと早く送信できてれば良かったな、と。でもこれでも部屋2位の成績で全体183位。前回、前々回の0完に比べればできた方。ただしこれで満足はしない。

レーティングは1268 → 1408 (+140)

以下ソース。

250 IncredibleMachine

重力加速度gについて二分探索してやればよい。気付くのにかかった時間を短縮できれば200点はいけてたと思う。ソース汚いのは仕様。

public class IncredibleMachine { 
    private double gett(double a, double b, double c) 
    { 
        return (-b + Math.Sqrt(b * b - 4 * a * c)) / (2 * a); 
    } 

    private double dist(int x0, int y0, int x1, int y1) 
    { 
        double dx = x1 - x0; 
        double dy = y1 - y0; 
        return Math.Sqrt(dx * dx + dy * dy); 
    } 

    public double gravitationalAcceleration(int[] x, int[] y, int T) { 
        double lo, hi, mid; 
        lo = 1e-12; 
        hi = 1e12; 
        while (hi - lo > 1e-9) 
        { 
            double v = 0.0, tt = 0.0; 
            mid = (hi + lo) / 2;    
            for (int i = 0; i < x.Length - 1; ++i) 
            { 
                double alpha = Math.Atan2(y[i] - y[i + 1], x[i + 1] - x[i]); 
                double a = mid * Math.Sin(alpha); 
                double t = gett(0.5 * a, v, -dist(x[i], y[i], x[i + 1], y[i + 1])); 
                tt += t; 
                v = v + a * t; 
            } 
            if (tt < T) 
            { 
                hi = mid; 
            } 
            else 
            { 
                lo = mid; 
            } 
        } 
        return lo; 
    } 
}