ABC279-E Cheating Amidakuji

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct EdgeDef
    {
        internal long EdgeNo;
        internal long FromNode;
        internal long ToNode;
    }
    static List<EdgeDef> mEdgeList = new List<EdgeDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long[] AArr = GetSplitArr(InputList[1]);

        foreach (long EachA in AArr) {
            EdgeDef WillAdd;
            WillAdd.EdgeNo = mEdgeList.Count + 1; ;
            WillAdd.FromNode = EachA;
            WillAdd.ToNode = EachA + 1;
            mEdgeList.Add(WillAdd);
        }
        long MaxEdgeNo = mEdgeList.Max(pX => pX.EdgeNo);

        // 1の位置[次に見る枝番号]なDict
        long CurrPos = 1;
        var Pos1Dict = new Dictionary<long, long>();
        Pos1Dict[1] = CurrPos;
        foreach (EdgeDef EachEdge in mEdgeList) {
            if (EachEdge.FromNode == CurrPos) {
                CurrPos = EachEdge.ToNode;
            }
            else if (EachEdge.ToNode == CurrPos) {
                CurrPos = EachEdge.FromNode;
            }
            if (EachEdge.EdgeNo + 1 <= MaxEdgeNo) {
                Pos1Dict[EachEdge.EdgeNo + 1] = CurrPos;
            }
        }

        // ゴール位置[ゴール値]なDict(逆方向)
        var RevAmidaDict = new Dictionary<long, long>();
        for (long I = 1; I <= N; I++) {
            RevAmidaDict[I] = I;
        }

        // 消す枝を、逆から全探索
        var AnswerList = new List<long>();
        foreach (EdgeDef EachEdge in mEdgeList.OrderByDescending(pX => pX.EdgeNo)) {
            long SeiPos = Pos1Dict[EachEdge.EdgeNo];
            long GoalPos = RevAmidaDict[SeiPos];
            AnswerList.Add(GoalPos);

            // 三角交換
            long FromNode = EachEdge.FromNode;
            long ToNode = EachEdge.ToNode;

            long tmp = RevAmidaDict[FromNode];
            RevAmidaDict[FromNode] = RevAmidaDict[ToNode];
            RevAmidaDict[ToNode] = tmp;
        }

        AnswerList.Reverse();
        AnswerList.ForEach(pX => Console.WriteLine(pX));
    }
}

C#のソース(枝ごとにSWAPした値を求める方法)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    class EdgeDef
    {
        internal long FromNode;
        internal long ToNode;
        internal long? Val1;
        internal long? Val2;
    }
    static List<EdgeDef> mEdgeList = new List<EdgeDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long[] AArr = GetSplitArr(InputList[1]);

        foreach (long EachA in AArr) {
            var WillAdd = new EdgeDef();
            WillAdd.FromNode = EachA;
            WillAdd.ToNode = EachA + 1;
            WillAdd.Val1 = null;
            WillAdd.Val2 = null;
            mEdgeList.Add(WillAdd);
        }

        // 値[Pos]なDict
        var ValDict = new Dictionary<long, long>();
        for (long I = 1; I <= N; I++) {
            ValDict[I] = I;
        }

        for (int I = 0; I <= mEdgeList.Count - 1; I++) {
            long FromNode = mEdgeList[I].FromNode;
            long ToNode = mEdgeList[I].ToNode;

            long FromVal = ValDict[FromNode];
            long ToVal = ValDict[ToNode];
            mEdgeList[I].Val1 = Math.Min(FromVal, ToVal);
            mEdgeList[I].Val2 = Math.Max(FromVal, ToVal);

            long tmp = ValDict[FromNode];
            ValDict[FromNode] = ValDict[ToNode];
            ValDict[ToNode] = tmp;
        }

        // あみだくじの一番下の、Pos[値]なDict
        var PosDict = new Dictionary<long, long>();
        foreach (var EachPair in ValDict) {
            PosDict[EachPair.Value] = EachPair.Key;
        }

        foreach (EdgeDef EachEdge in mEdgeList) {
            if (EachEdge.Val1 == 1) {
                Console.WriteLine(PosDict[EachEdge.Val2.Value]);
            }
            else if (EachEdge.Val2 == 1) {
                Console.WriteLine(PosDict[EachEdge.Val1.Value]);
            }
            else {
                Console.WriteLine(PosDict[1]);
            }
        }
    }
}

解説(前後からマージする方法)

以下のあみだくじの図で考えます。

1 2 3 4 5 6
| | | | | |
|-| | | | |
| |-| | | |
| | |-| | |
|-| | | | |
| | | |-| |
| |-| | | |
| | |-| | |
| | | | |-|
1 2 3 4 5 6

上からは、1の値がどこに移動するか？
下からは、バブルソートを意識しつつ、
横棒を、配列の交換をみなし、配列を持てば良いと分かります。
また、下からの処理は、MLE対策で、インプレースに行います。

後は、SWAPを枝とみなしてListに用意し、
消す枝を全探索すれば良いと分かります。

解説(枝ごとにSWAPした値を求める方法)

1    2    3    4
| 12 |    |    |
|----|    |    |
|    | 13 |    |
|    |----| 14 |
|    |    |----|
|    | 34 |    |
|    |----|    |
|    |    |    |
2    4    3    1

枝ごとにSWAPした2つの値を記憶して、
あみだくじの一番下の値を求めます。

それから、
枝ごとに、SWAPしなかった場合の、1の最終位置を求め、
解くことができます。