ABC-054-D Mixing Experiment

■■■問題■■■

イルカは、微量の物質Cを生成したいと考えています。
物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が Ma:Mb となる溶液を用意する必要があります。

しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。
薬局では、N種類の薬品を取り扱っており、各薬品iの在庫はちょうど1つです。
各薬品iは、タイプAの物質aiグラム、タイプBの物質biグラム含んでおり、価格ci円で売られています。

イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。
物質Cを生成するために、必要な最小予算を求めてください。
薬局で売られている薬品の組み合わせで、物質Cを生成できない場合はそれを報告してください。

■■■入力■■■

N Ma Mb
a1 b1 c1
a2 b2 c2
・
・
・
aN bN cN

●1 <= N <= 40
●1 <= ai,bi <= 10
●1 <= ci <= 100
●1 <= Ma,Mb <= 10
●gcd(Ma,Mb)=1
●ai、bi、ci、Ma、Mbは整数である

■■■出力■■■

物質Cを生成するために必要な最小予算を出力せよ。
物質Cを生成できない場合には-1を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 1 1");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 1 2");
            WillReturn.Add("3 3 10");
            //3
            //最小予算となる組み合わせは、薬品1と薬品2を混合する場合です。
            //この場合、混合した溶液中に物質Aは3グラム、物質Bは3グラム含まれており、
            //混合比は 3:3=1:1 となって条件を満たします。
            //このときの合計価格は3円となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1 10");
            WillReturn.Add("10 10 10");
            //-1
            //物質Aと物質Bの混合比が1:10となる薬品の組み合わせはないので、-1を出力します
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct YakuhinInfoDef
    {
        internal int A;
        internal int B;
        internal int C;
    }

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

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

        SplitAct(InputList[0]);
        int MA = wkArr[1];
        int MB = wkArr[2];

        var YakuhinInfoList = new List<YakuhinInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            YakuhinInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            WillAdd.C = wkArr[2];
            YakuhinInfoList.Add(WillAdd);
        }

        //最小金額[タイプAの合計,タイプBの合計]なDP表
        var PrevDP = new Dictionary<string, int>();
        PrevDP["0,0"] = 0;

        foreach (YakuhinInfoDef EachYakuhin in YakuhinInfoList) {
            var CurrDP = new Dictionary<string, int>(PrevDP);
            foreach (var EachPair in PrevDP) {
                string[] CurrStr = EachPair.Key.Split(',');
                int CurrA = int.Parse(CurrStr[0]);
                int CurrB = int.Parse(CurrStr[1]);

                int NewA = CurrA + EachYakuhin.A;
                int NewB = CurrB + EachYakuhin.B;
                int NewC = EachPair.Value + EachYakuhin.C;

                string NewKey = string.Format("{0},{1}", NewA, NewB);
                if (CurrDP.ContainsKey(NewKey)) {
                    if (CurrDP[NewKey] > NewC)
                        CurrDP[NewKey] = NewC;
                }
                else CurrDP[NewKey] = NewC;
            }
            PrevDP = CurrDP;
        }

        int Answer = int.MaxValue;
        bool HasAnswer = false;

        foreach (var EachPair in PrevDP) {
            string[] wkStr = EachPair.Key.Split(',');
            int CurrA = int.Parse(wkStr[0]);
            int CurrB = int.Parse(wkStr[1]);

            for (int I = 1; I < int.MaxValue; I++) {
                if (MA * I > CurrA) break;
                if (MB * I > CurrB) break;

                if (MA * I != CurrA) continue;
                if (MB * I != CurrB) continue;

                HasAnswer = true;
                if (Answer > EachPair.Value) {
                    Answer = EachPair.Value;
                }
            }
        }
        Console.WriteLine(HasAnswer ? Answer : -1);
    }
}

解説

最小金額[タイプAの合計,タイプBの合計]を更新する動的計画法の後で、
タイプAの合計:タイプBの合計が、条件を満たすかを判定してます。