ABC074-C Sugar Water

問題へのリンク

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("1 2 10 20 15 200");
            //110 10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 2 1 2 100 1000");
            //200 100
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("17 19 22 26 55 2802");
            //2634 934
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

            long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
            mA = wkArr[0];
            mB = wkArr[1];
            mC = wkArr[2];
            mD = wkArr[3];
            mE = wkArr[4];
            mF = wkArr[5];

            long[] WaterSumArr = ExecDFS(mA * 100, mB * 100);
            long[] SugarSumArr = ExecDFS(mC, mD);

            decimal Answer = decimal.MinValue;
            long AnswerWaterSum = 0;
            long AnswerSugarSum = 0;

            foreach (long EachWaterSum in WaterSumArr) {
                if (EachWaterSum == 0) continue; // 水が無しは、除外

                // 溶ける砂糖の上限
                long SugarSumLimit = EachWaterSum / 100 * mE;

                foreach (long EachSugarSum in SugarSumArr) {
                    // 質量は、F以下の必要あり
                    if (EachWaterSum + EachSugarSum > mF) break;

                    // 溶ける砂糖の上限と比較
                    if (EachSugarSum > SugarSumLimit) break;

                    decimal Bunsi = (decimal)(EachSugarSum * 100);
                    decimal Bunbo = (decimal)(EachWaterSum + EachSugarSum);
                    if (Bunbo > 0M) {
                        decimal AnswerKouho = Bunsi / Bunbo;

                        if (Answer < AnswerKouho) {
                            Answer = AnswerKouho;

                            AnswerWaterSum = EachWaterSum;
                            AnswerSugarSum = EachSugarSum;
                        }
                    }
                }
            }
            Console.WriteLine("{0} {1}", AnswerWaterSum + AnswerSugarSum, AnswerSugarSum);
        }
    }

    struct JyoutaiDef
    {
        internal long SumVal;
    }

    // DFSで、2つの数の和で作成可能な数の、配列を返す
    static long[] ExecDFS(long pBase1, long pBase2)
    {
        var WillReturn = new HashSet<long>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.SumVal = 0;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // 再訪防止
            if (WillReturn.Add(Popped.SumVal) == false)
                continue;

            WillPush.SumVal = Popped.SumVal + pBase1;
            if (WillPush.SumVal <= mF) Stk.Push(WillPush);

            WillPush.SumVal = Popped.SumVal + pBase2;
            if (WillPush.SumVal <= mF) Stk.Push(WillPush);
        }

        return WillReturn.OrderBy(pX => pX).ToArray();
    }
}

解説

深さ優先探索で、考えられる、水と砂糖の質量を列挙して、
全ての組合せを試してます。