ARC169-A Please Sign

問題へのリンク

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("4");
            WillReturn.Add("1 -2 3 -4");
            WillReturn.Add("1 2 3");
            //-
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 1 -1");
            WillReturn.Add("1 1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("1 -1 1 -1 1");
            WillReturn.Add("1 1 2 2");
            //+
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("20");
            WillReturn.Add("568273618 939017124 -32990462 -906026662 403558381 -811698210 56805591 0 436005733 -303345804 96409976 179069924 0 0 0 -626752087 569946496 0 0 0");
            WillReturn.Add("1 1 1 4 4 6 7 2 2 3 3 8 13 14 9 9 15 18 19");
            //+
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

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

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

        long[] PArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 逆辺の隣接リストを作成
        for (long I = 0; I <= PArr.GetUpperBound(0); I++) {
            long FromNode = PArr[I];
            long ToNode = I + 2;

            if (mToNodeListDict.ContainsKey(FromNode) == false) {
                mToNodeListDict[FromNode] = new List<long>();
            }
            mToNodeListDict[FromNode].Add(ToNode);
        }

        // 1から辺がない場合
        if (mToNodeListDict.ContainsKey(1) == false) {
            if (ADict[1] > 0) Console.WriteLine("+");
            if (ADict[1] == 0) Console.WriteLine("0");
            if (ADict[1] < 0) Console.WriteLine("-");
            return;
        }

        var ResultDFS = ExecDFS();
        var ResultDict = new Dictionary<long, long>();
        foreach (var EachItem in ResultDFS.GroupBy(pX => pX.Level)) {
            ResultDict[EachItem.Key] = EachItem.Sum(pX => ADict[pX.CurrNode]);
        }

        foreach (var EachPair in ResultDict.OrderByDescending(pX => pX.Key)) {
            if (EachPair.Value > 0) {
                ADict[1] = 1;
                break;
            }
            if (EachPair.Value < 0) {
                ADict[1] = -1;
                break;
            }
        }

        if (ADict[1] > 0) Console.WriteLine("+");
        if (ADict[1] == 0) Console.WriteLine("0");
        if (ADict[1] < 0) Console.WriteLine("-");
    }

    struct JyoutaiDef
    {
        internal long CurrNode;
        internal long Level;
    }

    static List<JyoutaiDef> ExecDFS()
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNode = 1;
        WillPush.Level = 1;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            WillReturn.Add(Popped);

            if (mToNodeListDict.ContainsKey(Popped.CurrNode) == false) {
                continue;
            }

            foreach (long EachToNode in mToNodeListDict[Popped.CurrNode]) {
                WillPush.CurrNode = EachToNode;
                WillPush.Level = Popped.Level + 1;
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

解説

考察すると、1のノードから逆辺をDFSし、
レベルごとのノード値のSumの符号に依存すると分かります。

最大レベルのノード値の合計が0なら、
最大レベル-1なレベルのノード値の合計を見る
といった対応も行う必要があります。