ABC184-F Programming Contest

問題へのリンク

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 17");
            WillReturn.Add("2 3 5 7 11");
            //17
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 100");
            WillReturn.Add("1 2 7 5 8 10");
            //33
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 100");
            WillReturn.Add("101 102 103 104 105 106");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("7 273599681");
            WillReturn.Add("6706927 91566569 89131517 71069699 75200339 98298649 92857057");
            //273555143
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mT;

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

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

        var OddList = new List<long>();
        var EvenList = new List<long>();

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I % 2 == 0) EvenList.Add(AArr[I]);
            if (I % 2 == 1) OddList.Add(AArr[I]);
        }

        List<JyoutaiDef> ExecDFSOdd = ExecDFS(OddList);
        List<JyoutaiDef> ExecDFSEven = ExecDFS(EvenList);

        var AnswerKouhoList = new List<long>();
        AnswerKouhoList.Add(0);

        var OddResultList = new List<long>();
        ExecDFSOdd.ForEach(pX => OddResultList.Add(pX.SumVal));
        OddResultList.Sort();

        var EvenResultList = new List<long>();
        ExecDFSEven.ForEach(pX => EvenResultList.Add(pX.SumVal));
        EvenResultList.Sort();

        AnswerKouhoList.AddRange(OddResultList);
        AnswerKouhoList.AddRange(EvenResultList);

        foreach (long EachVal in OddResultList) {
            long SearchVal = mT - EachVal;
            int LowerOrEqual_Max = ExecNibunhou_LowerOrEqual_Max(SearchVal, EvenResultList);
            if (LowerOrEqual_Max == -1) continue;
            AnswerKouhoList.Add(EachVal + EvenResultList[LowerOrEqual_Max]);
        }
        Console.WriteLine(AnswerKouhoList.Max());
    }

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

    static List<JyoutaiDef> ExecDFS(List<long> pList)
    {
        var WillReturn = new List<JyoutaiDef>();
        long UB = pList.Count - 1;

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (long I = 0; I <= UB; I++) {
            WillPush.CurrInd = I;
            WillPush.SumVal = pList[(int)I];
            Stk.Push(WillPush);
        }

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

            if (Popped.SumVal > mT) {
                continue;
            }
            WillReturn.Add(Popped);

            for (long I = Popped.CurrInd + 1; I <= UB; I++) {
                WillPush.CurrInd = I;
                WillPush.SumVal = Popped.SumVal + pList[(int)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;
    }
}

解説

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