TopCoder SRM579: MarblePositioning

|radius| は高々 8 なので全順列を全て試す。
半径 r1 の円と 半径 r2 の円を隣接するように置いた時の x 座標の差は

\(\sqrt{(r1+r2)^2 - (r1-r2)^2}\)

となる。

ただし 浮動小数点 で上記の数式を計算すると\((r1+r2)^2 - (r1-r2)^2\)の計算で\((r1+r2)\)と\((r1-r2)\)の値が近い場合に桁落ちが発生するため、誤差が発生しないように long で計算する必要がある。

または式を展開して、\(\sqrt{4 \times r1 \times r2}\) を使って計算しても桁落ちを回避できる。

よくわからないけど C++ だと桁落ちは発生しないらしい。ちなみにC♯だと桁落ちを考慮しないと最後のサンプルが通らない。

public class MarblePositioning {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }

    static public bool NextPermutation<T>(T[] array) where T : IComparable<T> {
        int n = array.Length;
        for (int i = n - 2; i >= 0; i--) {
            if (array[i].CompareTo(array[i + 1]) < 0) {
                var index = Array.FindLastIndex(array, v => array[i].CompareTo(v) < 0);
                Swap(ref array[i], ref array[index]);
                Array.Reverse(array, i + 1, n - (i + 1));
                return true;
            }
        }
        Array.Reverse(array);
        return false;
    }

    double distance(long r1, long r2) {
        return 2 * Math.Sqrt(r1 * r2);
    }

    public double totalWidth(int[] radius) {
        Array.Sort(radius);
        double ans = double.MaxValue;
        do {
            List<double> positions = new List<double>();
            positions.Add(0);
            for (int i = 1; i < radius.Length; i++) {
                double maxX = -1;
                for (int j = 0; j < i; j++) {
                    maxX = Math.Max(maxX, positions[j] + distance(radius[i], radius[j]));
                }
                positions.Add(maxX);
            }
            ans = Math.Min(ans, positions.Last());
        } while (NextPermutation(radius));
        return ans;
    }
}