AOJ 1357 Squeeze the Cylinders

問題

Squeeze the Cylinders | Aizu Online Judge

n個の円柱があり、それぞれの半径が与えられる。
円柱は地面に沿って転がして動かせるが、円柱の順番は入れ替えられない。
一列に並んだ円柱を両側から壁で押したとき、壁同士の最短距離はいくらになるか求めよ。

解法

左側の壁がx=0にあるとする。
i番目の円柱のx座標は、左側の壁に接している場合、0～i-1番目の円柱に接している場合のうち、最も遠いもの。
右側の壁は、0～n-1番目円柱に接している場合のうち、最も遠いもの。
n<=500なので、全て調べても間に合う。

ソースコード(C#)

using System;
using System.Collections.Generic;
using System.Linq;

namespace _1357
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double[] y = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double[] x = new double[n];
            double xmax = 0;
            for (int now = 0; now < n; now++)
            {
                double nowx = y[now];
                for (int bef = 0; bef < now; bef++)
                {
                    nowx = Math.Max(nowx, x[bef] + Math.Sqrt(Math.Pow(y[now] + y[bef], 2) - Math.Pow(y[now] - y[bef], 2)));
                }
                x[now] = nowx;
                xmax = Math.Max(xmax, x[now] + y[now]);
            }
            Console.WriteLine(xmax);
        }
    }
}