ABC415-E Hungry Takahashi

問題へのリンク

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");
            WillReturn.Add("3 2");
            WillReturn.Add("4 1");
            WillReturn.Add("1 3 6");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("5");
            WillReturn.Add("3");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 7");
            WillReturn.Add("35 29 36 88 58 15 25");
            WillReturn.Add("99 7 49 61 67 4 57");
            WillReturn.Add("96 92 3 49 49 36 90");
            WillReturn.Add("72 89 40 44 24 53 45");
            WillReturn.Add("55 43 23 71 77 6 94 19 27 21");
            //20
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long UB_X;
    static long UB_Y;

    static long[,] mBanArr;
    static long[] mCostArr;

    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]);
        long H = wkArr[0];
        long W = wkArr[1];
        UB_X = W - 1;
        UB_Y = H - 1;

        mBanArr = CreateBanArr(InputList.Skip(1).Take((int)H));

        SplitAct(InputList.Last());
        mCostArr = wkArr.ToArray();

        // 0が達成可能な場合
        if (CanAchieve(0)) {
            Console.WriteLine(0);
            return;
        }

        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)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    // K以下にできるかを返す
    static bool CanAchieve(long pK)
    {
        long?[,] MaxMoneyArr = new long?[UB_X + 1, UB_Y + 1];
        MaxMoneyArr[0, 0] = mBanArr[0, 0] + pK - mCostArr[0];
        if (MaxMoneyArr[0, 0] < 0) return false;

        for (long Y = 0; Y <= UB_Y; Y++) {
            for (long X = 0; X <= UB_X; X++) {
                if (MaxMoneyArr[X, Y].HasValue == false) continue;

                Action<long, long> SendAct = (pNewX, pNewY) =>
                {
                    if (pNewX > UB_X) return;
                    if (pNewY > UB_Y) return;

                    long TargetInd = pNewX + pNewY;
                    long NewVal = MaxMoneyArr[X, Y].Value + mBanArr[pNewX, pNewY] - mCostArr[TargetInd];
                    if (NewVal < 0) return;

                    if (MaxMoneyArr[pNewX, pNewY].HasValue) {
                        if (MaxMoneyArr[pNewX, pNewY] >= NewVal) {
                            return;
                        }
                    }
                    MaxMoneyArr[pNewX, pNewY] = NewVal;
                };

                SendAct(X, Y + 1);
                SendAct(X + 1, Y);
            }
        }
        bool Result = MaxMoneyArr[UB_X, UB_Y].HasValue;
        return Result;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をlongの2次元配列に設定
    ////////////////////////////////////////////////////////////////
    static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = new List<string>(pStrEnum);
        if (StrList.Count == 0) {
            return new long[0, 0];
        }

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

        SplitAct(StrList[0]);

        long UB_X = LongArr.GetUpperBound(0);
        long UB_Y = StrList.Count - 1;

        long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];

        for (long Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[(int)Y]);
            for (long X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = LongArr[X];
            }
        }
        return WillReturn;
    }
}

解説

答えを二分探索してます。