ABC404-D Goin' to the Zoo

問題へのリンク

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 3");
            WillReturn.Add("1000 300 700 200");
            WillReturn.Add("3 1 3 4");
            WillReturn.Add("3 1 2 4");
            WillReturn.Add("2 1 3");
            //1800
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 6");
            WillReturn.Add("500 500 500 500 500 500 1000");
            WillReturn.Add("3 1 2 7");
            WillReturn.Add("3 2 3 7");
            WillReturn.Add("3 3 4 7");
            WillReturn.Add("3 4 5 7");
            WillReturn.Add("3 5 6 7");
            WillReturn.Add("3 6 1 7");
            //2000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        SplitAct(InputList[0]);
        long ZooCnt = wkArr[0];
        long AnimalCnt = wkArr[1];

        SplitAct(InputList[1]);
        long[] CostArr = wkArr;

        // 見れる動物のSet[動物園]
        var WatchAnimalSetDict = new Dictionary<long, HashSet<long>>();
        for (int I = 1; I <= ZooCnt; I++) {
            WatchAnimalSetDict[I] = new HashSet<long>();
        }

        for (int I = 2; I <= InputList.Count - 1; I++) {
            SplitAct(InputList[I]);
            long[] ZooArr = wkArr.Skip(1).ToArray();

            long AnimalID = I - 2;
            foreach (long EachZoo in ZooArr) {
                WatchAnimalSetDict[EachZoo].Add(AnimalID);
            }
        }
        //foreach (var EachPair in WatchAnimalSetDict.OrderBy(pX => pX.Key)) {
        //    Console.WriteLine("動物園{0}で見れる動物", EachPair.Key);
        //    foreach (long EachAnimal in EachPair.Value) {
        //        Console.WriteLine(EachAnimal);
        //    }
        //}

        var BaseList = new List<int>();
        BaseList.Add(0);
        BaseList.Add(1);
        BaseList.Add(2);

        var AnswerList = new List<long>();

        foreach (int[] EachArr in RubyPatternClass<int>.RepeatedPermutation(BaseList, (int)ZooCnt)) {
            var WatchCntDict = new Dictionary<long, long>();
            long Cost = 0;
            for (long I = 0; I <= EachArr.GetUpperBound(0); I++) {
                long VisitCnt = EachArr[I];
                if (VisitCnt == 0) continue;

                Cost += CostArr[I] * VisitCnt;

                foreach (long EachAnimal in WatchAnimalSetDict[I + 1]) {
                    if (WatchCntDict.ContainsKey(EachAnimal) == false) {
                        WatchCntDict[EachAnimal] = 0;
                    }
                    WatchCntDict[EachAnimal] += VisitCnt;
                }
            }

            if (WatchCntDict.Count == AnimalCnt) {
                if (WatchCntDict.Values.All(pX => pX >= 2)) {
                    AnswerList.Add(Cost);
                }
            }
        }
        Console.WriteLine(AnswerList.Min());
    }
}

#region RubyPatternClass
// Rubyの場合の数
internal static class RubyPatternClass<Type>
{
    // 重複順列を返す
    private struct JyoutaiDef_RepeatedPermutation
    {
        internal List<int> SelectedIndList;
    }
    internal static IEnumerable<Type[]> RepeatedPermutation(IEnumerable<Type> pEnum, int pR)
    {
        if (pR == 0) yield break;
        Type[] pArr = pEnum.ToArray();

        var Stk = new Stack<JyoutaiDef_RepeatedPermutation>();
        JyoutaiDef_RepeatedPermutation WillPush;
        for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
            WillPush.SelectedIndList = new List<int>() { I };
            Stk.Push(WillPush);
        }

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

            // クリア判定
            if (Popped.SelectedIndList.Count == pR) {
                var WillReturn = new List<Type>();
                Popped.SelectedIndList.ForEach(X => WillReturn.Add(pArr[X]));
                yield return WillReturn.ToArray();
                continue;
            }

            for (int I = pArr.GetUpperBound(0); 0 <= I; I--) {
                WillPush.SelectedIndList = new List<int>(Popped.SelectedIndList) { I };
                Stk.Push(WillPush);
            }
        }
    }
}
#endregion

解説

動物園ごとの訪問回数を0回、1回、2回で
全探索してます。

各動物園の訪問回数は0回か2回のような
気もしますが、下記の反例があるのでダメです。

zoo1とzoo2とzoo3の入園料は100円とする。
動物1が、zoo1とzoo2で見れる。
動物2が、zoo1とzoo3で見れる。
動物3が、zoo2とzoo3で見れる。
と場合は、zoo1とzoo2とzoo3にそれぞれ1回入園するのが最適です。