ABC390-E Vitamin Balance

問題へのリンク

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 25");
            WillReturn.Add("1 8 5");
            WillReturn.Add("2 3 5");
            WillReturn.Add("2 7 10");
            WillReturn.Add("3 2 5");
            WillReturn.Add("3 3 10");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 5000");
            WillReturn.Add("1 200000 1");
            WillReturn.Add("2 200000 1");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mX;

    struct ItemInfoDef
    {
        internal long A;
        internal long C;
    }
    static List<ItemInfoDef> mItemInfoList1 = new List<ItemInfoDef>();
    static List<ItemInfoDef> mItemInfoList2 = new List<ItemInfoDef>();
    static List<ItemInfoDef> mItemInfoList3 = new List<ItemInfoDef>();

    static long?[] mDpResult1;
    static long?[] mDpResult2;
    static long?[] mDpResult3;

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

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        mX = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ItemInfoDef WillAdd;
            long V = wkArr[0];
            WillAdd.A = wkArr[1];
            WillAdd.C = wkArr[2];

            if (V == 1) mItemInfoList1.Add(WillAdd);
            if (V == 2) mItemInfoList2.Add(WillAdd);
            if (V == 3) mItemInfoList3.Add(WillAdd);
        }

        mDpResult1 = ExecDP(mItemInfoList1);
        mDpResult2 = ExecDP(mItemInfoList2);
        mDpResult3 = ExecDP(mItemInfoList3);

        long L = 0;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchieve(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // 3つともK以上取得できるかを返す
    static bool CanAchieve(long pNeedA)
    {
        long Result1 = NeedC(pNeedA, mDpResult1);
        long Result2 = NeedC(pNeedA, mDpResult2);
        long Result3 = NeedC(pNeedA, mDpResult3);

        return Result1 + Result2 + Result3 <= mX;
    }

    // 引数以上の摂取に必要な、最小カロリーを返す
    static long NeedC(long pNeedA, long?[] pDpResultArr)
    {
        for (long I = 0; I <= pDpResultArr.GetUpperBound(0); I++) {
            if (pDpResultArr[I].HasValue == false) continue;
            if (pDpResultArr[I].Value >= pNeedA) {
                return I;
            }
        }
        return long.MaxValue / 100;
    }

    // DP結果を返す
    static long?[] ExecDP(List<ItemInfoDef> pItemInfoList)
    {
        long UB = mX;

        // 摂取合計[カロリー]なDP表
        long?[] DPArr = new long?[UB + 1];
        DPArr[0] = 0;

        foreach (ItemInfoDef EachItem in pItemInfoList) {
            for (long I = UB; 0 <= I; I--) {
                if (DPArr[I].HasValue == false) continue;
                long NewI = I + EachItem.C;
                if (NewI > UB) continue;

                long NewVal = DPArr[I].Value + EachItem.A;

                if (DPArr[NewI].HasValue) {
                    if (DPArr[NewI] >= NewVal) {
                        continue;
                    }
                }
                DPArr[NewI] = NewVal;
            }
        }
        return DPArr;
    }
}

解説

最初にDPで
摂取合計[カロリー]なDP表
を作成します。

次に二分探索で
3つともK以上取得できるかを判定してます。