ABC076-D AtCoder Express

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("100");
            WillReturn.Add("30");
            //2100.000000000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("60 50");
            WillReturn.Add("34 38");
            //2632.000000000000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("12 14 2");
            WillReturn.Add("6 2 7");
            //76.000000000000000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1");
            WillReturn.Add("9");
            WillReturn.Add("10");
            //20.250000000000000000
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("10");
            WillReturn.Add("64 55 27 35 76 119 7 18 49 100");
            WillReturn.Add("29 19 31 39 27 48 41 87 55 70");
            //20291.000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // 時間の範囲ごとの上限速度
    struct SpeedLimitDef
    {
        internal double StaTime;
        internal double EndTime;
        internal double SpeedLimit;
    }
    static List<SpeedLimitDef> mSpeedLimitList = new List<SpeedLimitDef>();

    const double EPS = 0.5D;

    static void Main()
    {
        List<string> InputList = GetInputList();
        double[] TArr = InputList[1].Split(' ').Select(pX => double.Parse(pX)).ToArray();
        double[] VArr = InputList[2].Split(' ').Select(pX => double.Parse(pX)).ToArray();

        double BaseTime = 0;
        for (double I = 0; I <= TArr.GetUpperBound(0); I++) {
            SpeedLimitDef WillAdd;
            WillAdd.StaTime = BaseTime;
            WillAdd.EndTime = BaseTime + TArr[(int)I];
            WillAdd.SpeedLimit = VArr[(int)I];
            mSpeedLimitList.Add(WillAdd);
            BaseTime += TArr[(int)I];
        }
        double UB = VArr.Max();

        // 最大の移動距離[現在の速度]なDP表
        var PrevDP = new Dictionary<double, double>();
        PrevDP[0] = 0;

        double TSum = TArr.Sum();

        for (double I = EPS; I <= TSum; I += EPS) {
            var CurrDP = new Dictionary<double, double>();

            double SpeedLimit = DeriveSpeedLimit(I);
            foreach (var EachPair in PrevDP) {

                // 残時間と現在の速度で枝切り
                double RestT = TSum - I;
                if (0 < EachPair.Key - (RestT + 1)) continue;

                Action<double> UpdateAct = (pNewKey) =>
                {
                    if (pNewKey < 0 || SpeedLimit < pNewKey) return;

                    double NewVal = EachPair.Value + DeriveArea(EachPair.Key, pNewKey);
                    if (CurrDP.ContainsKey(pNewKey)) {
                        if (CurrDP[pNewKey] >= NewVal) {
                            return;
                        }
                    }
                    CurrDP[pNewKey] = NewVal;
                };

                UpdateAct(EachPair.Key - EPS); // 速度を減らす
                UpdateAct(EachPair.Key);       // 速度を変えない
                UpdateAct(EachPair.Key + EPS); // 速度を増やす
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[0]);
    }

    // EPS秒前の速度と、現在の速度を引数として、台形の面積を返す
    static double DeriveArea(double pPrevSpeed, double pCurrSpeed)
    {
        return (pPrevSpeed + pCurrSpeed) * EPS / 2.0D;
    }

    // 時間を引数として、制限速度を返す
    static double DeriveSpeedLimit(double pTime)
    {
        double SpeedLimit = double.MaxValue;
        foreach (SpeedLimitDef EachSpeedLimit in mSpeedLimitList) {
            if (EachSpeedLimit.StaTime <= pTime && pTime <= EachSpeedLimit.EndTime) {
                SpeedLimit = Math.Min(SpeedLimit, EachSpeedLimit.SpeedLimit);
            }
            if (pTime < EachSpeedLimit.EndTime) break;
        }
        return SpeedLimit;
    }
}

解説

積分を意識して、
速度を増やす、変えない、減らすの三択でDPしてます。