ABC271-D Flip and Adjust

問題へのリンク

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

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }

    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 S = wkArr[1];

        var ABList = new List<ABInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            ABList.Add(WillAdd);
        }
        int UB = ABList.Count - 1;

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.SumVal = 0;
        WillPush.Path = "";
        Stk.Push(WillPush);

        // 和 * 1000 + 現在添字
        var VisitedSet = new HashSet<int>();

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

            if (Popped.CurrInd > UB) {
                if (Popped.SumVal == S) {
                    Console.WriteLine("Yes");
                    Console.WriteLine(Popped.Path);
                    return;
                }
                continue;
            }

            Action<int, string> PushAct = (pAddVal, pAddStr) =>
            {
                WillPush.CurrInd = Popped.CurrInd + 1;
                WillPush.SumVal = Popped.SumVal + pAddVal;
                WillPush.Path = Popped.Path + pAddStr;
                int Hash = WillPush.SumVal * 1000 + WillPush.CurrInd;
                if (VisitedSet.Add(Hash)) {
                    Stk.Push(WillPush);
                }
            };

            // 表を使う場合
            PushAct(ABList[Popped.CurrInd].A, "H");

            // 裏を使う場合
            PushAct(ABList[Popped.CurrInd].B, "T");
        }
        Console.WriteLine("No");
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int SumVal;
        internal string Path;
    }
}

解説

状態に、{現在添字、和、パス}を持ってDFSしてます。

和と現在添字とからなるハッシュ値で
訪問済なら枝切りしてます。