ABC192-F Potion

問題へのリンク

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("3 9999999999");
            WillReturn.Add("3 6 8");
            //4999999994
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1000000000000000000");
            WillReturn.Add("1");
            //999999999999999999
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mX;
    static long[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mX = wkArr[1];

        mAArr = GetSplitArr(InputList[1]);

        var AnswerList = new List<long>();
        for (long I = 1; I <= mAArr.Length; I++) {
            long?[,] ResultDP = ExecDP(I);

            for (long J = 0; J <= ResultDP.GetUpperBound(0); J++) {
                if (ResultDP[I, J].HasValue) {
                    long CurrVal = ResultDP[I, J].Value;
                    long Diff = mX - CurrVal;
                    if (Diff % I > 0) {
                        continue;
                    }
                    AnswerList.Add(Diff / I);
                }
            }
        }
        Console.WriteLine(AnswerList.Min());
    }

    // 取得数を引数とし、解候補を返す
    static long?[,] ExecDP(long pTakeCnt)
    {
        long UB = pTakeCnt;

        // 最大スコア[現在の取得数 , mod 取得数] なインラインDP表
        long?[,] DPArr = new long?[UB + 1, UB + 1];
        DPArr[0, 0] = 0;

        foreach (long EachA in mAArr) {
            for (long I = UB; 0 <= I; I--) {
                for (long J = UB; 0 <= J; J--) {
                    if (DPArr[I, J].HasValue == false) continue;

                    long NewI = I + 1;
                    long NewVal = DPArr[I, J].Value + EachA;
                    long NewJ = NewVal % pTakeCnt;

                    if (NewI > UB) continue;

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

解説

制約のXの下限が十分に大きいことをふまえると、
Nの上限が100なので
最大スコア[現在の取得数 , mod 取得数]を更新するDPを100回行うとしても

100*100*100*100 = 10の8乗
なので間に合うと分かります。