ABC013-C 節制

問題へのリンク

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("4 5");
            WillReturn.Add("100 4 60 1 4");
            //160
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 1");
            WillReturn.Add("5000 2 2000 1 300");
            //20000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 23");
            WillReturn.Add("170 8 120 5 12");
            //650
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("653 314159");
            WillReturn.Add("6728 123456 5141 41928 222222");
            //2818162
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mH;

    static long mA;
    static long mB;
    static long mC;
    static long mD;
    static long mE;

    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]);
        mN = wkArr[0];
        mH = wkArr[1];

        SplitAct(InputList[1]);
        mA = wkArr[0];
        mB = wkArr[1];
        mC = wkArr[2];
        mD = wkArr[3];
        mE = wkArr[4];

        // 普通の食事をする回数を全探索
        long Answer = long.MaxValue;
        for (long I = 0; I <= mN; I++) {
            long MinSissoCnt = DeriveMinSissoCnt(I);

            long AnswerKouho = I * mA + MinSissoCnt * mC;
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }

    // 普通の食事回数を引数とし、質素な食事の最小値を返す
    static long DeriveMinSissoCnt(long pHutuuCnt)
    {
        long RestDay = mN - pHutuuCnt;
        long CurrH = mH + mB * pHutuuCnt;

        // 0回が可能な場合
        if (CurrH - mE * RestDay > 0) {
            return 0;
        }

        long L = 0;
        long R = RestDay;

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

            long RestH = CurrH + Mid * mD - (RestDay - Mid) * mE;

            if (RestH > 0) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}

解説

普通の食事をする回数を全探索し、
質素な食事回数の最小値は、二分法で求めてます。