ABC335-E Non-Decreasing Colorful Path

問題へのリンク

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

    static Dictionary<long, long> mNodeValDict = new Dictionary<long, long>();

    static long mN;

    // 隣接リスト(HashSet)
    static Dictionary<long, HashSet<long>> mToNodeSetDict = new Dictionary<long, HashSet<long>>();

    static long mStaNode;
    static long mGoalNode;

    // UnionFind後の頂点情報
    struct NodeInfoDef
    {
        internal long RootNode;
        internal long NodeVal;
    }
    static List<NodeInfoDef> mNodeInfoList = new List<NodeInfoDef>();

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

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            mNodeValDict[I + 1] = AArr[I];
        }

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

        SplitAct(InputList[0]);

        mN = wkArr[0];

        var InsUnionFind = new UnionFind();
        for (long I = 1; I <= mN; I++) {
            InsUnionFind.MakeSet(I);
        }

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];

            long FromVal = mNodeValDict[FromNode];
            long ToVal = mNodeValDict[ToNode];

            if (FromVal == ToVal) {
                InsUnionFind.Unite(FromNode, ToNode);
            }
        }

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            FromNode = InsUnionFind.FindSet(FromNode);
            ToNode = InsUnionFind.FindSet(ToNode);
            if (FromNode == ToNode) continue;

            if (mToNodeSetDict.ContainsKey(FromNode) == false) {
                mToNodeSetDict[FromNode] = new HashSet<long>();
            }
            if (mToNodeSetDict.ContainsKey(ToNode) == false) {
                mToNodeSetDict[ToNode] = new HashSet<long>();
            }

            long FromVal = mNodeValDict[FromNode];
            long ToVal = mNodeValDict[ToNode];
            if (FromVal < ToVal) {
                mToNodeSetDict[FromNode].Add(ToNode);
            }
            if (ToVal < FromVal) {
                mToNodeSetDict[ToNode].Add(FromNode);
            }
        }

        mStaNode = InsUnionFind.FindSet(1);
        mGoalNode = InsUnionFind.FindSet(mN);

        for (long I = 1; I <= mN; I++) {
            long RootNode = InsUnionFind.FindSet(I);
            if (RootNode != I) continue;

            NodeInfoDef WillAdd;
            WillAdd.RootNode = I;
            WillAdd.NodeVal = mNodeValDict[I];
            mNodeInfoList.Add(WillAdd);
        }

        ExecDP();
    }

    static void ExecDP()
    {
        // 最大スコア[ノード]なDP表
        var DPDict = new Dictionary<long, long>();
        DPDict[mStaNode] = 1;

        // 頂点の数値の昇順にDP
        var Query = mNodeInfoList.OrderBy(pX => pX.NodeVal);
        foreach (NodeInfoDef EachNodeInfo in Query) {
            long CurrNode = EachNodeInfo.RootNode;
            if (DPDict.ContainsKey(CurrNode) == false) {
                continue;
            }
            long CurrVal = DPDict[CurrNode];

            long RootNode = EachNodeInfo.RootNode;
            if (mToNodeSetDict.ContainsKey(RootNode) == false) {
                continue;
            }

            foreach (long EachToNode in mToNodeSetDict[RootNode]) {
                Action<long> UpdateAct = (pNewVal) =>
                {
                    if (DPDict.ContainsKey(EachToNode)) {
                        if (DPDict[EachToNode] >= pNewVal) {
                            return;
                        }
                    }
                    DPDict[EachToNode] = pNewVal;
                };
                UpdateAct(CurrVal + 1);
            }
        }

        if (DPDict.ContainsKey(mGoalNode)) {
            Console.WriteLine(DPDict[mGoalNode]);
        }
        else {
            Console.WriteLine(0);
        }
    }
}

#region UnionFind
// UnionFindクラス
internal class UnionFind
{
    private class NodeInfoDef
    {
        internal long ParentNode;
        internal long Rank;
    }
    private Dictionary<long, NodeInfoDef> mNodeInfoDict =
        new Dictionary<long, NodeInfoDef>();

    // 要素が1つである木を森に追加
    internal void MakeSet(long pNode)
    {
        NodeInfoDef WillAdd = new NodeInfoDef();
        WillAdd.ParentNode = pNode;
        WillAdd.Rank = 0;
        mNodeInfoDict[pNode] = WillAdd;
    }

    // 合併処理
    internal void Unite(long pX, long pY)
    {
        long XNode = FindSet(pX);
        long YNode = FindSet(pY);
        long XRank = mNodeInfoDict[XNode].Rank;
        long YRank = mNodeInfoDict[YNode].Rank;

        if (XRank > YRank) {
            mNodeInfoDict[YNode].ParentNode = XNode;
        }
        else {
            mNodeInfoDict[XNode].ParentNode = YNode;
            if (XRank == YRank) {
                mNodeInfoDict[YNode].Rank++;
            }
        }
    }

    // ノードを引数として、木の根を取得
    internal long FindSet(long pTargetNode)
    {
        // 根までの経路上のノードのList
        var PathNodeList = new List<long>();

        long CurrNode = pTargetNode;
        while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
            PathNodeList.Add(CurrNode);
            CurrNode = mNodeInfoDict[CurrNode].ParentNode;
        }

        // 経路圧縮 (親ポインタの付け替え)
        foreach (long EachPathNode in PathNodeList) {
            mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
        }
        return CurrNode;
    }

    internal void DebugPrint()
    {
        foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
            Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
                EachPair.Key, EachPair.Value.ParentNode);
        }
    }
}
#endregion

解説

UnionFindで頂点の数値が同じで連結したノードをまとめてから、
DAGになるように連結リストで辺を管理し、
DAGなので、頂点の数値の昇順にDPしてます。