典型90問 051 Typical Shop（★5）

問題へのリンク

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 2 10");
            WillReturn.Add("3 8 7 5 11");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 1 10");
            WillReturn.Add("7 7 7 7 7");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("40 20 100");
            WillReturn.Add("1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5");
            //137846528820
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long mP;

    static List<long> mAList1 = new List<long>();
    static List<long> mAList2 = new List<long>();

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

        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];
        mP = wkArr[2];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I % 2 == 0) mAList1.Add(AArr[I]);
            if (I % 2 == 1) mAList2.Add(AArr[I]);
        }

        // 半分全列挙
        List<JyoutaiDef> ResultList1 = ExecDFS(mAList1);
        List<JyoutaiDef> ResultList2 = ExecDFS(mAList2);

        // 個数ごとに合計のListを作る
        var ResultListDict = new Dictionary<long, List<long>>();
        foreach (JyoutaiDef EachJyoutai in ResultList2) {
            long CurrCnt = EachJyoutai.Cnt;
            if (ResultListDict.ContainsKey(CurrCnt) == false) {
                ResultListDict[CurrCnt] = new List<long>();
            }
            ResultListDict[CurrCnt].Add(EachJyoutai.SumVal);
        }

        // 合計の昇順にソートしておく
        foreach (var EachPair in ResultListDict) {
            EachPair.Value.Sort();
        }

        long Answer = 0;
        foreach (JyoutaiDef EachJyoutai in ResultList1) {
            long RestCnt = mK - EachJyoutai.Cnt;
            if (ResultListDict.ContainsKey(RestCnt) == false) {
                continue;
            }
            List<long> pList = ResultListDict[RestCnt];
            int ResultInd = ExecNibunhou_LowerOrEqual_Max(mP - EachJyoutai.SumVal, pList);
            if (ResultInd == -1) continue;
            Answer += ResultInd + 1;
        }
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal long Cnt;
        internal int CurrInd;
        internal long SumVal;
    }

    static List<JyoutaiDef> ExecDFS(List<long> pList)
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Cnt = 0;
        WillPush.CurrInd = 0;
        WillPush.SumVal = 0;
        Stk.Push(WillPush);

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

            // 枝切り
            if (Popped.SumVal > mP) continue;

            WillReturn.Add(Popped);

            for (int I = Popped.CurrInd; I <= pList.Count - 1; I++) {
                WillPush.Cnt = Popped.Cnt + 1;
                WillPush.CurrInd = I + 1;
                WillPush.SumVal = Popped.SumVal + pList[I];
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList.Last()) {
            return pList.Count - 1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

半分全列挙と二分探索を組み合わせてます。