DPL_4_B: コインの組み合わせ II

問題へのリンク

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("2 2 1 9");
            WillReturn.Add("5 1");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 2 7 19");
            WillReturn.Add("3 5 4 2 2");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long mL;
    static long mR;
    static long[] mAArr;
    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];
        mL = wkArr[2];
        mR = wkArr[3];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        List<JyoutaiDef> ListOdd = ExecDFS(true);
        List<JyoutaiDef> ListEven = ExecDFS(false);

        long Answer = 0;

        // 単独解があれば計上その1
        foreach (JyoutaiDef EachJyoutai in ListOdd) {
            if (EachJyoutai.Cnt == mK) {
                if (mL <= EachJyoutai.SumVal && EachJyoutai.SumVal <= mR) {
                    Answer++;
                }
            }
        }

        // 単独解があれば計上その2
        foreach (JyoutaiDef EachJyoutai in ListEven) {
            if (EachJyoutai.Cnt == mK) {
                if (mL <= EachJyoutai.SumVal && EachJyoutai.SumVal <= mR) {
                    Answer++;
                }
            }
        }

        // 個数ごとのSumのList
        var SumArrDict = new Dictionary<long, List<long>>();
        foreach (JyoutaiDef EachJyoutai in ListEven) {
            long Cnt = EachJyoutai.Cnt;
            if (SumArrDict.ContainsKey(Cnt) == false) {
                SumArrDict[Cnt] = new List<long>();
            }
            SumArrDict[Cnt].Add(EachJyoutai.SumVal);
        }

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

        foreach (JyoutaiDef EachJyoutai in ListOdd) {
            long RestCnt = mK - EachJyoutai.Cnt;
            if (SumArrDict.ContainsKey(RestCnt)) {
                List<long> pList = SumArrDict[RestCnt];
                long RangeMin = mL - EachJyoutai.SumVal;
                long RangeMax = mR - EachJyoutai.SumVal;

                int ResutInd1 = ExecNibunhou_LowerBound(RangeMin, pList);
                int ResutInd2 = ExecNibunhou_LowerOrEqual_Max(RangeMax, pList);

                if (ResutInd1 == -1) continue;
                if (ResutInd2 == -1) continue;

                Answer += ResutInd2 - ResutInd1 + 1;
            }
        }
        Console.WriteLine(Answer);
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return 0;
        }

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

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

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

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素が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;
    }

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

    static List<JyoutaiDef> ExecDFS(bool pIsOdd)
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (long I = 0; I <= UB; I++) {
            bool IsOK = false;
            if (pIsOdd && I % 2 == 0) {
                IsOK = true;
            }
            if (pIsOdd == false && I % 2 == 1) {
                IsOK = true;
            }

            if (IsOK) {
                WillPush.Cnt = 1;
                WillPush.SumVal = mAArr[I];
                WillPush.CurrInd = I + 2;
                Stk.Push(WillPush);
            }
        }

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

            for (long I = Popped.CurrInd; I <= UB; I += 2) {
                WillPush.Cnt = Popped.Cnt + 1;
                WillPush.SumVal = Popped.SumVal + mAArr[I];
                WillPush.CurrInd = I + 2;

                if (WillPush.Cnt > mK) continue;
                if (WillPush.SumVal > mR) continue;

                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

解説

半分全探索してます。