ARC139-B Make N

問題へのリンク

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");
            WillReturn.Add("10 3 5 2 3 6");
            WillReturn.Add("10 3 5 1 1000000000 1000000000");
            WillReturn.Add("139 2 139 1 1 1");
            WillReturn.Add("139 1 1 1 1 1");
            WillReturn.Add("139 7 10 3845 26982 30923");
            //11
            //10
            //1
            //139
            //436604
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            long N = wkArr[0];
            long A = wkArr[1];
            long B = wkArr[2];
            long X = wkArr[3];
            long Y = wkArr[4];
            long Z = wkArr[5];

            long Result = Solve(N, A, B, X, Y, Z);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long pN, long pA, long pB, long pX, long pY, long pZ)
    {
        // Yを緩和
        pY = Math.Min(pY, pX * pA);

        // Zを緩和
        pZ = Math.Min(pZ, pX * pB);

        // コスト1で増加できる値(コスパ)は、AとYのペアの方が多い状態にする
        if (pA * pZ < pY * pB) {
            Swap(ref pA, ref  pB);
            Swap(ref pY, ref  pZ);
        }

        long LoopACnt = pN / pA;
        long LoopBCnt = pA;

        var AnswerKouhoList = new List<long>();

        if (LoopACnt < LoopBCnt) {
            for (long I = 0; I <= LoopACnt; I++) {
                long AnswerKouho = 0;
                AnswerKouho += I * pY;

                long Rest = pN - I * pA;
                if (Rest < 0) continue;
                long Syou = Rest / pB;
                AnswerKouho += Syou * pZ;
                Rest -= pB * Syou;

                AnswerKouho += Rest * pX;

                AnswerKouhoList.Add(AnswerKouho);
            }
        }
        else {
            for (long I = 0; I <= LoopBCnt; I++) {
                long AnswerKouho = 0;
                AnswerKouho += I * pZ;

                long Rest = pN - I * pB;
                if (Rest < 0) continue;
                long Syou = Rest / pA;
                AnswerKouho += Syou * pY;
                Rest -= pA * Syou;

                AnswerKouho += Rest * pX;

                AnswerKouhoList.Add(AnswerKouho);
            }
        }
        return AnswerKouhoList.Min();
    }

    static void Swap(ref long p1, ref long p2)
    {
        long tmp = p1;
        p1 = p2;
        p2 = tmp;
    }
}

解説

最初に
1増やすのを繰り返すほうが最適かで
コストYとコストZを緩和します。

次に、
A増やすのにコストYかかる
B増やすのにコストZかかる
で1増やすにかかるコストが少ない(コスパがいい)
ほうを調べ、
A増やすのにコストYかかる
ほうがコスパがいいように、必要ならSwapします。

すると
A増やす回数を、0回から、N/A 回 の全探索か
B増やす回数を、0回から、(A-1)回の全探索
で解けるので、回数の少ないほうを選択してます。