ABC363-F Palindromic Expression

問題へのリンク

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("363");
            //11*3*11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("101");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3154625100");
            //2*57*184481*75*2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ParentInfoDef
    {
        internal long Val1;
        internal long Val2;
    }
    static Dictionary<long, ParentInfoDef> ParentInfoDict = new Dictionary<long, ParentInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

        var Stk = new Stack<long>();
        long WillPush;
        WillPush = N;
        Stk.Push(WillPush);

        bool HasAnswer = false;
        bool HasZero;
        long LeafVal = 0;
        while (Stk.Count > 0) {
            long Popped = Stk.Pop();

            var CurrNumList = DeriveNumList(Popped, out HasZero);
            if (HasZero == false && IsKaibun(CurrNumList)) {
                LeafVal = Popped;
                HasAnswer = true;
                break;
            }

            long[] YakusuuArr = DeriveYakusuuArr(Popped);
            for (int I = 0; I <= YakusuuArr.GetUpperBound(0); I++) {
                if (YakusuuArr[I] == 1) continue;
                var NumList1 = DeriveNumList(YakusuuArr[I], out HasZero);
                if (HasZero) continue;
                for (int J = I; J <= YakusuuArr.GetUpperBound(0); J++) {
                    if (YakusuuArr[I] * YakusuuArr[J] > Popped) break;
                    if ((Popped / YakusuuArr[I]) % YakusuuArr[J] > 0) continue;

                    var NumList2 = DeriveNumList(YakusuuArr[J], out HasZero);
                    if (HasZero) continue;

                    if (IsOKPair(NumList1, NumList2)) {
                        WillPush = Popped / YakusuuArr[I] / YakusuuArr[J];
                        if (ParentInfoDict.ContainsKey(WillPush) == false) {
                            ParentInfoDef WillAdd;
                            WillAdd.Val1 = YakusuuArr[I];
                            WillAdd.Val2 = YakusuuArr[J];
                            ParentInfoDict[WillPush] = WillAdd;

                            Stk.Push(WillPush);
                        }
                    }
                }
            }
        }

        if (HasAnswer == false) {
            Console.WriteLine(-1);
            return;
        }

        var InsLinkedList = new LinkedList<long>();
        InsLinkedList.AddFirst(LeafVal);

        long CurrVal = LeafVal;
        while (ParentInfoDict.ContainsKey(CurrVal)) {
            ParentInfoDef CurrParentInfo = ParentInfoDict[CurrVal];
            InsLinkedList.AddFirst(CurrParentInfo.Val1);
            InsLinkedList.AddLast(CurrParentInfo.Val2);
            CurrVal *= CurrParentInfo.Val1 * CurrParentInfo.Val2;
        }
        Console.WriteLine(LongEnumJoin("*", InsLinkedList));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

    // 約数を列挙する
    static long[] DeriveYakusuuArr(long pTarget)
    {
        var YakusuuSet = new HashSet<long>();
        for (long I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }
        long[] YakusuuArr = YakusuuSet.ToArray();
        Array.Sort(YakusuuArr);
        return YakusuuArr;
    }

    static List<long> DeriveNumList(long pVal, out bool pHasZero)
    {
        pHasZero = false;
        var WIllReturn = new List<long>();
        while (pVal > 0) {
            long ModVal = pVal % 10;
            if (ModVal == 0) {
                pHasZero = true;
            }
            WIllReturn.Add(ModVal);
            pVal /= 10;
        }
        return WIllReturn;
    }

    // List2つを引数とし、OKなペアかを返す
    static bool IsOKPair(List<long> pList1, List<long> pList2)
    {
        if (pList1.Count != pList2.Count) return false;
        int UB = pList1.Count - 1;
        for (int I = 0; I <= UB; I++) {
            int PairInd = UB - I;
            if (pList1[I] != pList2[PairInd]) return false;
        }
        return true;
    }

    // Listを引数とし、回文数かを返す
    static bool IsKaibun(List<long> pList)
    {
        int UB = pList.Count - 1;
        for (int I = 0; I <= UB / 2; I++) {
            int PairInd = UB - I;
            if (pList[I] != pList[PairInd]) return false;
        }
        return true;
    }
}

解説

親ノードの情報をDictで持つDFSで解いてます。