Hatena::Grouptopcoder

yambe2002の日記

 | 

2016-01-29

SRM579 Div2 Hard: MarblePositioning(練習)

11:42

さまざまな半径のビー玉を一直線に並べた時に、最初のビー玉の接地点と最後のビー玉の接地点の距離を最小にする。

ビー玉の数が少ないので、全パターンをチェックすればよい。

最初IntからDoubleへのキャストを忘れてSystemtestで落としてしまった。

public class MarblePositioning {

    static void Swap<T>(ref T a, ref T b)
    {
        T tmp;
        tmp = a;
        a = b;
        b = tmp;
    }

    static void GetPermutation<T>(ref List<T[]> ret, T[] arry, int i, int n)
    {
        int j;
        if (i == n)
            ret.Add(new List<T>(arry).ToArray());
        else
        {
            for (j = i; j <= n; j++)
            {
                Swap(ref arry[i], ref arry[j]);
                GetPermutation(ref ret, arry, i + 1, n);
                Swap(ref arry[i], ref arry[j]); //backtrack
            }
        }
    }

    double GetDistOfTwoMarbles(int a, int b)
    {
        return 2 * Math.Sqrt((double)a * (double)b);    //キャストを忘れない!
    }

    double GetPosition(int idx, List<int> prevBalls, List<double> prevPositions, int[] radius)
    {
        double ret = 0.0;

        var currentBallRadius = radius[idx];
        for (int prevIdx = 0; prevIdx < prevBalls.Count(); prevIdx++)
        {
            var prevBall = prevBalls[prevIdx];
            var prevBallRadius = radius[prevBall];
            var prevBallPosition = prevPositions[prevIdx];

            var pos = prevBallPosition + GetDistOfTwoMarbles(currentBallRadius, prevBallRadius);
            ret = Math.Max(ret, pos);
        }

        return ret;
    }

    double GetDist(int[] pattern, int[] radius)
    {
        var balls = new List<int>();
        balls.Add(pattern.First());

        var positions = new List<double>();
        positions.Add(0);

        for(int idx = 1; idx < pattern.Length; idx++)
        {
            positions.Add(GetPosition(pattern[idx], balls, positions, radius));
            balls.Add(pattern[idx]);
        }

        return positions.Last();
    }

    public double totalWidth(int[] radius) {
        double res = double.MaxValue;

        var indices = Enumerable.Range(0, radius.Length).ToArray();
        var permutations = new List<int[]>();
        GetPermutation(ref permutations, indices, 0, radius.Length - 1);

        foreach(var pattern in permutations)
        {
            var dist = GetDist(pattern, radius);
            if(dist < res) res = dist;
        }

        return res;
    }
}
 |