Q50 戦闘力で考えるモンスターの組み合わせ

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Solve(8);
        Solve(50);
    }

    static void Solve(int pMaxVal)
    {
        int AnswerCnt = 0;
        for (int I = 1; I <= pMaxVal; I++) {
            for (int J = I + 1; J <= pMaxVal; J++) {
                for (int K = J + 1; K <= pMaxVal; K++) {
                    var Selected3List = new List<int>() { I, J, K };

                    if (IsValidList(Selected3List) == false) {
                        continue;
                    }

                    for (int L = K + 1; L <= pMaxVal; L++) {
                        var Selected4List = new List<int>() { I, J, K, L };

                        if (IsValidList(Selected4List) == false) {
                            continue;
                        }

                        AnswerCnt++;
                        Console.WriteLine("解{0}を発見{1},{2},{3},{4}", AnswerCnt, I, J, K, L);
                    }
                }
            }
        }
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int Sum1;
        internal int Sum2;
        internal int Sum3;
        internal int Sum4;
    }

    // DFSで、和が等しくなる組み合わせがないかを調べる
    static bool IsValidList(List<int> pValList)
    {
        int UB = pValList.Count - 1;

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 1;
        WillPush.Sum1 = pValList[0];
        WillPush.Sum2 = 0;
        WillPush.Sum3 = 0;
        WillPush.Sum4 = 0;
        Stk.Push(WillPush);

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

            if (IsOK(Popped.Sum1, Popped.Sum2, Popped.Sum3, Popped.Sum4) == false) {
                return false;
            }

            if (Popped.CurrInd > UB) {
                continue;
            }

            Action<int> PushAct = (pAddSum) =>
            {
                WillPush.CurrInd = Popped.CurrInd + 1;
                WillPush.Sum1 = Popped.Sum1;
                WillPush.Sum2 = Popped.Sum2;
                WillPush.Sum3 = Popped.Sum3;
                WillPush.Sum4 = Popped.Sum4;

                if (pAddSum == 1) WillPush.Sum1 += pValList[Popped.CurrInd];
                if (pAddSum == 2) WillPush.Sum2 += pValList[Popped.CurrInd];
                if (pAddSum == 3) WillPush.Sum3 += pValList[Popped.CurrInd];
                if (pAddSum == 4) WillPush.Sum4 += pValList[Popped.CurrInd];
                Stk.Push(WillPush);
            };

            PushAct(1);
            PushAct(2);
            PushAct(3);
            PushAct(4);
        }
        return true;
    }

    // 和が等しい組み合わせの有無を調べる
    static bool IsOK(int pSum1, int pSum2, int pSum3, int pSum4)
    {
        Func<int, int, bool> IsOKFunc = (p1, p2) =>
        {
            if (p1 == 0) return true;
            return p1 != p2;
        };

        if (IsOKFunc(pSum1, pSum2) == false) return false;
        if (IsOKFunc(pSum1, pSum3) == false) return false;
        if (IsOKFunc(pSum1, pSum4) == false) return false;

        if (IsOKFunc(pSum2, pSum3) == false) return false;
        if (IsOKFunc(pSum2, pSum4) == false) return false;

        if (IsOKFunc(pSum3, pSum4) == false) return false;

        return true;
    }
}

実行結果

省略
解191225を発見45,47,49,50
解191226を発見45,48,49,50
解191227を発見46,47,48,50
解191228を発見46,48,49,50

解説

DFSで、戦闘力が同じになる組み合わせの有無を調べてます。