第5回PAST F 一触即発

問題へのリンク

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 2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("1 2 4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 7");
            WillReturn.Add("1 2 5");
            WillReturn.Add("2 3 5");
            WillReturn.Add("2 4 5");
            WillReturn.Add("1 2 3");
            WillReturn.Add("4 5 6");
            WillReturn.Add("2 5 6");
            WillReturn.Add("1 3 5");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 1");
            WillReturn.Add("1 2 3");
            //1
        }
        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();

        SplitAct(InputList[0]);
        int N = wkArr[0];

        var NGSetList = new List<HashSet<int>>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            var CurrSet = new HashSet<int>();
            CurrSet.Add(wkArr[0]);
            CurrSet.Add(wkArr[1]);
            CurrSet.Add(wkArr[2]);
            NGSetList.Add(CurrSet);
        }

        int Answer = 0;

        int CompleteBit = (1 << N) - 1;
        for (int I = 0; I <= CompleteBit; I++) {
            var SelectedSet = new HashSet<int>();
            for (int J = 1; J <= N; J++) {
                int CurrBit = (1 << (J - 1));
                if ((I & CurrBit) > 0) {
                    SelectedSet.Add(J);
                }
            }

            // 既に爆発する組み合わせならNG
            bool IsNG = false;
            foreach (HashSet<int> EachNGSet in NGSetList) {
                if (EachNGSet.IsSubsetOf(SelectedSet)) {
                    IsNG = true;
                }
            }
            if (IsNG) continue;

            // 追加したら爆発する薬品の数を集計する
            int AnswerKouho = 0;
            for (int J = 1; J <= N; J++) {
                if (SelectedSet.Contains(J)) continue;
                var NewSet = new HashSet<int>(SelectedSet);
                NewSet.Add(J);

                foreach (HashSet<int> EachNGSet in NGSetList) {
                    if (EachNGSet.IsSubsetOf(NewSet)) {
                        AnswerKouho++;
                        break;
                    }
                }
            }
            Answer = Math.Max(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }
}

解説

Bit全探索で、全ての薬品の組み合わせを列挙してます。