ABC095-D Static Sushi

問題へのリンク

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("3 20");
            WillReturn.Add("2 80");
            WillReturn.Add("9 120");
            WillReturn.Add("16 1");
            //191
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 20");
            WillReturn.Add("2 80");
            WillReturn.Add("9 1");
            WillReturn.Add("16 120");
            //192
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 100000000000000");
            WillReturn.Add("50000000000000 1");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("15 10000000000");
            WillReturn.Add("400000000 1000000000");
            WillReturn.Add("800000000 1000000000");
            WillReturn.Add("1900000000 1000000000");
            WillReturn.Add("2400000000 1000000000");
            WillReturn.Add("2900000000 1000000000");
            WillReturn.Add("3300000000 1000000000");
            WillReturn.Add("3700000000 1000000000");
            WillReturn.Add("3800000000 1000000000");
            WillReturn.Add("4000000000 1000000000");
            WillReturn.Add("4100000000 1000000000");
            WillReturn.Add("5200000000 1000000000");
            WillReturn.Add("6600000000 1000000000");
            WillReturn.Add("8000000000 1000000000");
            WillReturn.Add("9300000000 1000000000");
            WillReturn.Add("9700000000 1000000000");
            //6500000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mC;

    struct XVInfoDef
    {
        internal long X;
        internal long V;
    }
    static List<XVInfoDef> mXVInfoList = new List<XVInfoDef>();
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        mC = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XVInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.V = wkArr[1];
            mXVInfoList.Add(WillAdd);
        }
        UB = mXVInfoList.Count - 1;

        // X座標の昇順にソートしておく
        mXVInfoList = mXVInfoList.OrderBy(pX => pX.X).ToList();

        var AnswerKouhoList = new List<long>();
        long Kouho01 = DeriveKouho01();
        AnswerKouhoList.Add(Kouho01);

        long Kouho02 = DeriveKouho02();
        AnswerKouhoList.Add(Kouho02);

        long Kouho03 = DeriveKouho03();
        AnswerKouhoList.Add(Kouho03);

        Console.WriteLine(AnswerKouhoList.Max());
    }

    // 解候補01 右にひらすら進んだ時の最大値を返す
    static long DeriveKouho01()
    {
        long CurrVal = 0;
        long CurrPos = 0;
        long Answer = 0;
        foreach (XVInfoDef EachXVInfo in mXVInfoList) {
            CurrVal -= EachXVInfo.X - CurrPos;
            CurrPos = EachXVInfo.X;
            CurrVal += EachXVInfo.V;
            Answer = Math.Max(Answer, CurrVal);
        }
        return Answer;
    }

    // 解候補02 左にひらすら進んだ時の最大値を返す
    static long DeriveKouho02()
    {
        long CurrVal = 0;
        long CurrPos = mC;
        long Answer = 0;
        foreach (XVInfoDef EachXVInfo in mXVInfoList.AsEnumerable().Reverse()) {
            CurrVal -= CurrPos - EachXVInfo.X;
            CurrPos = EachXVInfo.X;
            CurrVal += EachXVInfo.V;
            Answer = Math.Max(Answer, CurrVal);
        }
        return Answer;
    }

    // 解候補03 左に進んでから、原点に戻って、右に進む時の最大値を返す
    static long DeriveKouho03()
    {
        long[] RunMaxArr1 = DeriveRunMaxArr(false);
        long[] RunMaxArr2 = DeriveRunMaxArr(true);

        // 左にどこまで進むかを全探索
        long CurrVal = 0;
        long CurrPos = mC;
        long Answer = 0;
        for (int I = UB; 1 <= I; I--) {
            CurrVal -= CurrPos - mXVInfoList[I].X;
            CurrPos = mXVInfoList[I].X;
            CurrVal += mXVInfoList[I].V;

            int LeftLen = UB - I + 1;
            long BackCost = mC - CurrPos;

            // 左に移動してから、右に移動する場合
            long RunMax1 = RunMaxArr1[UB - LeftLen];
            long AnswerKouho1 = CurrVal - BackCost + RunMax1;

            // 右に移動してから、左に移動する場合
            long RunMax2 = RunMaxArr2[UB - LeftLen];
            long AnswerKouho2 = CurrVal + RunMax2;

            Answer = Math.Max(Answer, AnswerKouho1);
            Answer = Math.Max(Answer, AnswerKouho2);
        }
        return Answer;
    }

    // 原点からの最大値を求め、累積最大値も求める。移動コストの2倍フラグも持つ
    static long[] DeriveRunMaxArr(bool pMoveCost2)
    {
        long[] WillReturn = new long[mXVInfoList.Count];

        long CurrVal = 0;
        long CurrPos = 0;
        long CurrValMax = long.MinValue;

        for (int I = 0; I <= mXVInfoList.Count - 1; I++) {
            if (pMoveCost2) {
                CurrVal -= (mXVInfoList[I].X - CurrPos) * 2;
            }
            else {
                CurrVal -= mXVInfoList[I].X - CurrPos;
            }
            CurrPos = mXVInfoList[I].X;
            CurrVal += mXVInfoList[I].V;

            CurrValMax = Math.Max(CurrValMax, CurrVal);
            WillReturn[I] = CurrValMax;
        }
        return WillReturn;
    }
}

解説

解候補は、下記の4通りになります。

解候補01 右にひたすら進んだ時の最大値
解候補02 左にひたすら進んだ時の最大値
解候補03 左に進んでから、原点に戻って、右に進む時の最大値
解候補04 右に進んでから、原点に戻って、左に進む時の最大値

解候補03と解候補04は、
左端と右端が同じであれば、
移動コストが2倍になる区間の違いだけ分かります。

以上により、解候補01と解候補02は、ナイーブに全探索。
解候補03は、
原点から右に進む場合の、
添字ごとの累積Maxを求めておいて、
左にどこまで進むかを全探索して、
移動コストが2倍になる区間は、2通りを試してます。