ABC119-C Synthetic Kadomatsu

問題へのリンク

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 100 90 80");
            WillReturn.Add("98");
            WillReturn.Add("40");
            WillReturn.Add("30");
            WillReturn.Add("21");
            WillReturn.Add("80");
            //23
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 100 90 80");
            WillReturn.Add("100");
            WillReturn.Add("100");
            WillReturn.Add("90");
            WillReturn.Add("90");
            WillReturn.Add("90");
            WillReturn.Add("80");
            WillReturn.Add("80");
            WillReturn.Add("80");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 1000 800 100");
            WillReturn.Add("300");
            WillReturn.Add("333");
            WillReturn.Add("400");
            WillReturn.Add("444");
            WillReturn.Add("500");
            WillReturn.Add("555");
            WillReturn.Add("600");
            WillReturn.Add("666");
            //243
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal List<int> BaseListOfA;
        internal List<int> BaseListOfB;
        internal List<int> BaseListOfC;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];
        int A = wkArr[1];
        int B = wkArr[2];
        int C = wkArr[3];

        int[] LArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();

        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.BaseListOfA = new List<int>();
        WillPush.BaseListOfB = new List<int>();
        WillPush.BaseListOfC = new List<int>();

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

        var KouhoCombiList = new List<JyoutaiDef>();

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

            if (Popped.BaseListOfA.Count > 0
                && Popped.BaseListOfB.Count > 0
                && Popped.BaseListOfC.Count > 0) {
                KouhoCombiList.Add(Popped);
            }

            if (Popped.CurrInd > N) continue;

            for (int I = Popped.CurrInd; I <= LArr.GetUpperBound(0); I++) {
                //Aに使用
                WillPush.CurrInd = I + 1;
                WillPush.BaseListOfA = new List<int>(Popped.BaseListOfA) { LArr[I] };
                WillPush.BaseListOfB = Popped.BaseListOfB;
                WillPush.BaseListOfC = Popped.BaseListOfC;
                Stk.Push(WillPush);

                //Bに使用
                WillPush.CurrInd = I + 1;
                WillPush.BaseListOfA = Popped.BaseListOfA;
                WillPush.BaseListOfB = new List<int>(Popped.BaseListOfB) { LArr[I] };
                WillPush.BaseListOfC = Popped.BaseListOfC;
                Stk.Push(WillPush);

                //Cに使用
                WillPush.CurrInd = I + 1;
                WillPush.BaseListOfA = Popped.BaseListOfA;
                WillPush.BaseListOfB = Popped.BaseListOfB;
                WillPush.BaseListOfC = new List<int>(Popped.BaseListOfC) { LArr[I] };
                Stk.Push(WillPush);
            }
        }
        //foreach (JyoutaiDef EachKouhoCombi in KouhoCombiList) {
        //    var sb = new System.Text.StringBuilder();
        //    sb.Append("Aの候補"); EachKouhoCombi.BaseListOfA.ForEach(pX => sb.AppendFormat("{0},", pX));
        //    sb.Append("Bの候補"); EachKouhoCombi.BaseListOfB.ForEach(pX => sb.AppendFormat("{0},", pX));
        //    sb.Append("Cの候補"); EachKouhoCombi.BaseListOfC.ForEach(pX => sb.AppendFormat("{0},", pX));
        //    Console.WriteLine(sb.ToString());
        //}
        Console.WriteLine(KouhoCombiList.Min(pX => Solve(pX, A, B, C)));
    }

    //組合せを引数として、コストを返す
    static int Solve(JyoutaiDef pKouhoCombi, int pA, int pB, int pC)
    {
        int Cost = 0;

        Action<List<int>, int> DeriveCostFunc = (pList, pGoal) =>
        {
            int CurrNum = pList[0];
            for (int I = 1; I <= pList.Count - 1; I++) {
                CurrNum += pList[I];
                Cost += 10;
            }

            Cost += Math.Abs(CurrNum - pGoal);
        };
        DeriveCostFunc(pKouhoCombi.BaseListOfA, pA);
        DeriveCostFunc(pKouhoCombi.BaseListOfB, pB);
        DeriveCostFunc(pKouhoCombi.BaseListOfC, pC);

        return Cost;
    }
}

解説

Nの制約が3以上8以下なので
A,B,Cのどの竹として使うかを
全探索してます。

Aに使う、Bに使う、Cに使う、使わない
で高々、4の8乗 = 65536通り になります。