ABC415-C Mixture

問題へのリンク

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");
            WillReturn.Add("3");
            WillReturn.Add("0010000");
            WillReturn.Add("3");
            WillReturn.Add("0010110");
            WillReturn.Add("1");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("100");
            WillReturn.Add("4");
            WillReturn.Add("001110010101110");
            //Yes
            //No
            //No
            //Yes
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            int N = int.Parse(InputList[I]);
            string S = InputList[I + 1];
            string Result = Solve(N, S);
            Console.WriteLine(Result);
        }
    }

    static string Solve(int pN, string pS)
    {
        int AllBitOn = (1 << pN) - 1;

        // NGな状態のSet
        var NGSet = new HashSet<int>();
        for (int I = 0; I <= pS.Length - 1; I++) {
            if (pS[I] == '1') {
                NGSet.Add(I + 1);
            }
        }

        // 到達可能状態のSet
        var PrevDP = new HashSet<int>();
        PrevDP.Add(0);

        while (PrevDP.Count > 0) {
            var CurrDP = new HashSet<int>();
            foreach (var EachJyoutai in PrevDP) {
                for (int I = 1; I <= pN; I++) {
                    int CurrBit = 1 << (I - 1);
                    if ((EachJyoutai & CurrBit) > 0) {
                        continue;
                    }
                    int NewVal = EachJyoutai + CurrBit;
                    if (NGSet.Contains(NewVal)) {
                        continue;
                    }
                    CurrDP.Add(NewVal);
                }
            }
            PrevDP = CurrDP;

            if (PrevDP.Contains(AllBitOn)) {
                return "Yes";
            }
        }
        return "No";
    }
}

解説

最初にNGなBitSetのHashSetを用意し、
到達可能状態でBitDPしてます。