ABC369-F Gather Coins

問題へのリンク

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

    class CoinPosDef
    {
        internal int X;
        internal int Y;
    }
    static List<CoinPosDef> mCoinPosList = new List<CoinPosDef>();

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

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

        SplitAct(InputList[0]);
        int GoalX = wkArr[1];
        int GoalY = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            var WillAdd = new CoinPosDef();
            WillAdd.X = wkArr[1];
            WillAdd.Y = wkArr[0];
            mCoinPosList.Add(WillAdd);
        }

        mCoinPosList = mCoinPosList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToList();

        // LISの最終値の最小値[LISの長さ] なDP表
        var DPSortedList = new SortedList<int, int>();

        // 更新した座標[LISの長さ]なDict
        var UpdatePosDict = new Dictionary<int, string>();

        // 親の座標[子の座標]なDict
        var ParentPosDict = new Dictionary<string, string>();

        foreach (CoinPosDef EachCoinPos in mCoinPosList) {
            int CurrY = EachCoinPos.Y;
            string Hash = GetHash(EachCoinPos.X, EachCoinPos.Y);
            if (DPSortedList.Count == 0) {
                DPSortedList[1] = CurrY;
                UpdatePosDict[1] = Hash;
                ParentPosDict[Hash] = "";
                continue;
            }
            int UpsertKeyInd = ExecNibunhou(DPSortedList, CurrY);

            int CurrUB = DPSortedList.Count - 1;
            var Keys = DPSortedList.Keys;

            // 更新する位置によって分岐
            if (UpsertKeyInd <= CurrUB) {
                DPSortedList[Keys[UpsertKeyInd]] = CurrY;
                UpdatePosDict[Keys[UpsertKeyInd]] = Hash;
                int PrevLength = Keys[UpsertKeyInd] - 1;
                if (PrevLength >= 1) {
                    ParentPosDict[Hash] = UpdatePosDict[PrevLength];
                }
            }
            else {
                int PrevKey = Keys[CurrUB];
                DPSortedList[PrevKey + 1] = CurrY;
                UpdatePosDict[PrevKey + 1] = Hash;
                ParentPosDict[Hash] = UpdatePosDict[PrevKey];
            }
        }
        int AnswerLisLength = DPSortedList.Keys.Max();
        Console.WriteLine(AnswerLisLength);

        var AnswerPosList = new List<string>();
        string CurrPos = UpdatePosDict[AnswerLisLength];
        while (true) {
            AnswerPosList.Add(CurrPos);

            if (ParentPosDict.ContainsKey(CurrPos)) {
                CurrPos = ParentPosDict[CurrPos];
            }
            else {
                break;
            }
        }
        AnswerPosList.Reverse();

        // 答えの文字列を作成
        var sb = new System.Text.StringBuilder();
        int PosX = 1;
        int PosY = 1;
        foreach (string EachCoinPos in AnswerPosList) {
            if (EachCoinPos == "") continue;

            string[] SplitArr = EachCoinPos.Split(',');
            int NextX = int.Parse(SplitArr[0]);
            int NextY = int.Parse(SplitArr[1]);

            if (PosX < NextX) {
                sb.Append('R', NextX - PosX);
                PosX = NextX;
            }
            if (PosY < NextY) {
                sb.Append('D', NextY - PosY);
                PosY = NextY;
            }
        }

        if (PosX < GoalX) {
            sb.Append('R', GoalX - PosX);
        }
        if (PosY < GoalY) {
            sb.Append('D', GoalY - PosY);
        }
        Console.WriteLine(sb.ToString());
    }

    // 座標を引数として、ハッシュ値を返す
    static string GetHash(int pX, int pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }

    // 二分法で、引数の値を設定する、キーの配列の添字を返す
    static int ExecNibunhou(SortedList<int, int> pDPSortedList, int pTargetVal)
    {
        int UB = pDPSortedList.Count - 1;
        var Keys = pDPSortedList.Keys;

        // 最小値未満の場合
        if (pTargetVal < pDPSortedList[Keys[0]]) {
            return 0;
        }

        // 最大値以上の場合
        if (pTargetVal >= pDPSortedList[Keys[UB]]) {
            return UB + 1;
        }

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;
            if (pDPSortedList[Keys[Mid]] <= pTargetVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return R;
    }
}

解説

広義単調増加のLISを求めれば良いので、
LISの最終値の最小値[LISの長さ]を更新するDPを行い、
DP復元してます。