AOJ 0551 つらら

問題へのリンク

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("4 6");
            WillReturn.Add("4");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("5");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 10");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("1");
            WillReturn.Add("9");
            WillReturn.Add("5");
            WillReturn.Add("1");
            //15
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct TuraraInfoDef
    {
        internal long InitLen;
        internal long Pos;
    }
    static List<TuraraInfoDef> mTuraraInfoList = new List<TuraraInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long LenLimit = wkArr[1];

        long[] InitLenArr = InputList.Skip(1).Select(pX => long.Parse(pX)).ToArray();
        long UB = InitLenArr.GetUpperBound(0);

        long[] WaitLeftArr = new long[UB + 1];
        long[] WaitRightArr = new long[UB + 1];

        for (long I = 0; I <= UB; I++) {
            TuraraInfoDef WillAdd;
            WillAdd.InitLen = InitLenArr[I];
            WillAdd.Pos = I;
            mTuraraInfoList.Add(WillAdd);
        }
        mTuraraInfoList = mTuraraInfoList.OrderByDescending(pX => pX.InitLen).ToList();

        var Answer = new List<long>();
        foreach (TuraraInfoDef EachTuraraInfo in mTuraraInfoList) {
            long WaitTime = Math.Max(WaitLeftArr[EachTuraraInfo.Pos], WaitRightArr[EachTuraraInfo.Pos]);
            WaitTime += LenLimit - EachTuraraInfo.InitLen;
            Answer.Add(WaitTime);

            Action<long, long, bool> AddAct = (pTargetPos, pAddVal, pWaitLeft) =>
            {
                if (pTargetPos < 0 || UB < pTargetPos) return;
                if (InitLenArr[pTargetPos] > EachTuraraInfo.InitLen) return;

                if (pWaitLeft) {
                    WaitLeftArr[pTargetPos] += pAddVal;
                }
                else {
                    WaitRightArr[pTargetPos] += pAddVal;
                }
            };
            AddAct(EachTuraraInfo.Pos - 1, WaitTime, false);
            AddAct(EachTuraraInfo.Pos + 1, WaitTime, true);
        }
        Console.WriteLine(Answer.Max());
    }
}

解説

氷柱の長さの降順にシュミレーションしてます。
氷柱ごとに、左の氷柱に待たされる時間と、右の氷柱に待たされる時間を持つようにしてます。