ABC197-E Traveler

問題へのリンク

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

    struct XCInfoDef
    {
        internal long X;
        internal long C;
    }

    // 色ごとの最小X座標と最大X座標
    struct PosInfoDef
    {
        internal long MinX;
        internal long MaxX;
    }
    static Dictionary<long, PosInfoDef> mPosInfoDict = new Dictionary<long, PosInfoDef>();

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

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

        var XCInfoList = new List<XCInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XCInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.C = wkArr[1];
            XCInfoList.Add(WillAdd);
        }

        foreach (var EachItem in XCInfoList.GroupBy(pX => pX.C)) {
            PosInfoDef WillAdd;
            WillAdd.MinX = EachItem.Min(pX => pX.X);
            WillAdd.MaxX = EachItem.Max(pX => pX.X);
            mPosInfoDict[EachItem.Key] = WillAdd;
        }

        Solve();
    }

    static void Solve()
    {
        // 最小コスト[X座標]なDP表
        var PrevDP = new Dictionary<long, long>();
        PrevDP[0] = 0;

        foreach (var EachPosInfo in mPosInfoDict.OrderBy(pX => pX.Key)) {
            var CurrDP = new Dictionary<long, long>();
            foreach (var EachPrevDP in PrevDP) {

                Action<long, long> UpsertAct = (pNewKey, pNewVal) =>
                {
                    if (CurrDP.ContainsKey(pNewKey)) {
                        if (CurrDP[pNewKey] <= pNewVal) {
                            return;
                        }
                    }
                    CurrDP[pNewKey] = pNewVal;
                };

                long MaxMinDiff = Math.Abs(EachPosInfo.Value.MaxX
                                         - EachPosInfo.Value.MinX);

                // 右端に移動してから、左端に移動する場合
                long NewKey1 = EachPosInfo.Value.MinX;
                long NewVal1 = EachPrevDP.Value;
                NewVal1 += Math.Abs(EachPrevDP.Key - EachPosInfo.Value.MaxX);
                NewVal1 += MaxMinDiff;
                UpsertAct(NewKey1, NewVal1);

                // 左端に移動してから、右端に移動する場合
                long NewKey2 = EachPosInfo.Value.MaxX;
                long NewVal2 = EachPrevDP.Value;
                NewVal2 += Math.Abs(EachPrevDP.Key - EachPosInfo.Value.MinX);
                NewVal2 += MaxMinDiff;
                UpsertAct(NewKey2, NewVal2);
            }
            PrevDP = CurrDP;
        }

        long Answer = long.MaxValue;
        foreach (var EachPair in PrevDP) {
            long AnswerKouho = EachPair.Value + Math.Abs(EachPair.Key);
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }
}

解説

昇順に取っていく必要があるので、
最小のX座標に移動してから最大のX座標に移動する方法と
最大のX座標に移動してから最小のX座標に移動する方法の
2通りの遷移を可能にした、
最小コスト[X座標]を更新するDPで解いてます。