ABC375-E 3 Team Division

問題へのリンク

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("6");
            WillReturn.Add("1 2");
            WillReturn.Add("2 5");
            WillReturn.Add("1 5");
            WillReturn.Add("3 3");
            WillReturn.Add("1 3");
            WillReturn.Add("3 6");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 1");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1 1");
            WillReturn.Add("2 1");
            WillReturn.Add("3 1");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("12");
            WillReturn.Add("2 5");
            WillReturn.Add("1 4");
            WillReturn.Add("3 3");
            WillReturn.Add("2 3");
            WillReturn.Add("3 9");
            WillReturn.Add("1 2");
            WillReturn.Add("2 2");
            WillReturn.Add("3 9");
            WillReturn.Add("2 6");
            WillReturn.Add("1 9");
            WillReturn.Add("1 1");
            WillReturn.Add("3 1");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal long A;
        internal long B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        long SumB = mABInfoList.Sum(pX => pX.B);
        if (SumB % 3 > 0) {
            Console.WriteLine(-1);
            return;
        }

        long NeedSum = SumB / 3;

        // 最小コスト[状態]なDP表
        var PrevDP = new Dictionary<long, long>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.Sum1 = 0;
        FirstJyoutai.Sum2 = 0;
        FirstJyoutai.Sum3 = 0;
        PrevDP[GetHash(FirstJyoutai)] = 0;

        foreach (ABInfoDef EachABInfo in mABInfoList) {
            var CurrDP = new Dictionary<long, long>();

            Action<long, long, long, long> UpdateAct =
                (pNewSum1, pNewSum2, pNewSum3, pNewCost) =>
                {
                    JyoutaiDef NewJyoutai;
                    NewJyoutai.Sum1 = pNewSum1;
                    NewJyoutai.Sum2 = pNewSum2;
                    NewJyoutai.Sum3 = pNewSum3;

                    // 枝切り
                    if (pNewSum1 > NeedSum) return;
                    if (pNewSum2 > NeedSum) return;
                    if (pNewSum3 > NeedSum) return;

                    long NewHash = GetHash(NewJyoutai);
                    if (CurrDP.ContainsKey(NewHash)) {
                        if (CurrDP[NewHash] <= pNewCost) {
                            return;
                        }
                    }
                    CurrDP[NewHash] = pNewCost;
                };

            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                long CurrSum1 = CurrJyoutai.Sum1;
                long CurrSum2 = CurrJyoutai.Sum2;
                long CurrSum3 = CurrJyoutai.Sum3;
                if (EachABInfo.A == 1) {
                    UpdateAct(CurrSum1 + EachABInfo.B, CurrSum2, CurrSum3, EachPair.Value);
                    UpdateAct(CurrSum1, CurrSum2 + EachABInfo.B, CurrSum3, EachPair.Value + 1);
                    UpdateAct(CurrSum1, CurrSum2, CurrSum3 + EachABInfo.B, EachPair.Value + 1);
                }
                if (EachABInfo.A == 2) {
                    UpdateAct(CurrSum1 + EachABInfo.B, CurrSum2, CurrSum3, EachPair.Value + 1);
                    UpdateAct(CurrSum1, CurrSum2 + EachABInfo.B, CurrSum3, EachPair.Value);
                    UpdateAct(CurrSum1, CurrSum2, CurrSum3 + EachABInfo.B, EachPair.Value + 1);
                }
                if (EachABInfo.A == 3) {
                    UpdateAct(CurrSum1 + EachABInfo.B, CurrSum2, CurrSum3, EachPair.Value + 1);
                    UpdateAct(CurrSum1, CurrSum2 + EachABInfo.B, CurrSum3, EachPair.Value + 1);
                    UpdateAct(CurrSum1, CurrSum2, CurrSum3 + EachABInfo.B, EachPair.Value);
                }
            }
            PrevDP = CurrDP;
        }

        var AnswerList = new List<long>();
        foreach (var EachPair in PrevDP) {
            JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);
            if (CurrJyoutai.Sum1 != NeedSum) continue;
            if (CurrJyoutai.Sum2 != NeedSum) continue;
            if (CurrJyoutai.Sum3 != NeedSum) continue;
            AnswerList.Add(EachPair.Value);
        }
        if (AnswerList.Count == 0) {
            Console.WriteLine(-1);
        }
        else {
            Console.WriteLine(AnswerList.Min());
        }
    }

    struct JyoutaiDef
    {
        internal long Sum1;
        internal long Sum2;
        internal long Sum3;
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.Sum1;
        Hash *= 10000;
        Hash += pJyoutai.Sum2;
        Hash *= 10000;
        Hash += pJyoutai.Sum3;
        return Hash;
    }

    static JyoutaiDef GetJyoutai(long pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.Sum3 = pHash % 10000;
        pHash /= 10000;
        WillReturn.Sum2 = pHash % 10000;
        pHash /= 10000;
        WillReturn.Sum1 = pHash;
        return WillReturn;
    }
}

解説

全員の強さの合計は不変量なので
3チームの強さが一致するとしたら、
(全員の強さの合計 / 3)以外はありえないと分かります。

そして、
最小コスト[状態]でDPしてます。

チーム移動したらコストがかかるではなく、
人ごとに、
チームAに所属するのはコスト0
チームBに所属するのはコスト1
チームCに所属するのはコスト1
と考えて、
人のループで所属チームを決めるDPとしてます。

また、強さがマイナスの人がいないので、
強さ合計で枝切りしてます。