ARC121-B RGB Matching

問題へのリンク

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");
            WillReturn.Add("1 R");
            WillReturn.Add("2 G");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("1 B");
            WillReturn.Add("2 B");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("585 B");
            WillReturn.Add("293 B");
            WillReturn.Add("788 B");
            WillReturn.Add("222 B");
            WillReturn.Add("772 G");
            WillReturn.Add("841 B");
            WillReturn.Add("115 R");
            WillReturn.Add("603 G");
            WillReturn.Add("450 B");
            WillReturn.Add("325 R");
            WillReturn.Add("851 B");
            WillReturn.Add("205 G");
            WillReturn.Add("134 G");
            WillReturn.Add("651 R");
            WillReturn.Add("565 R");
            WillReturn.Add("548 B");
            WillReturn.Add("391 G");
            WillReturn.Add("19 G");
            WillReturn.Add("808 B");
            WillReturn.Add("475 B");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ItemInfoDef
    {
        internal long Val;
        internal char Color;
    }

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

        var ItemList = new List<ItemInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');

            ItemInfoDef WillAdd;
            WillAdd.Val = long.Parse(SplitArr[0]);
            WillAdd.Color = SplitArr[1][0];
            ItemList.Add(WillAdd);
        }

        var RList = ItemList.Where(pX => pX.Color == 'R').ToList();
        var GList = ItemList.Where(pX => pX.Color == 'G').ToList();
        var BList = ItemList.Where(pX => pX.Color == 'B').ToList();
        long RCnt = RList.Count;
        long GCnt = GList.Count;
        long BCnt = BList.Count;

        // 3色とも個数が偶数の場合
        if (RCnt % 2 == 0 && GCnt % 2 == 0 && BCnt % 2 == 0) {
            Console.WriteLine(0);
            return;
        }

        if (RCnt % 2 == 0) Console.WriteLine(Solve(GList, BList, RList));
        if (GCnt % 2 == 0) Console.WriteLine(Solve(RList, BList, GList));
        if (BCnt % 2 == 0) Console.WriteLine(Solve(RList, GList, BList));
    }

    // 奇数List2つと偶数Listでの解を返す
    static long Solve(List<ItemInfoDef> pOddList1, List<ItemInfoDef> pOddList2, List<ItemInfoDef> pEvenList)
    {
        var AnswerKouhoList = new List<long>();

        // 解候補1
        var UnionList = new List<ItemInfoDef>();
        UnionList.AddRange(pOddList1);
        UnionList.AddRange(pOddList2);
        UnionList = UnionList.OrderBy(pX => pX.Val).ToList();

        for (int I = 0; I <= UnionList.Count - 2; I++) {
            if (UnionList[I].Color != UnionList[I + 1].Color) {
                long AnswerKouho = Math.Abs(UnionList[I].Val - UnionList[I + 1].Val);
                AnswerKouhoList.Add(AnswerKouho);
            }
        }

        // 解候補2
        if (pEvenList.Count >= 2) {
            long[] RValArr = pOddList1.Select(pX => pX.Val).ToArray();
            long[] GValArr = pOddList2.Select(pX => pX.Val).ToArray();
            Array.Sort(RValArr);
            Array.Sort(GValArr);
            long[] BValArr = pEvenList.Select(pX => pX.Val).ToArray();

            // 最小値[Rの数,Gの数,Bの数]なDP表
            long?[, ,] DPArr = new long?[2, 2, 3];
            DPArr[0, 0, 0] = 0;

            foreach (long EachEvenVal in BValArr) {
                for (int I = 1; 0 <= I; I--) {
                    for (int J = 1; 0 <= J; J--) {
                        for (int K = 2; 0 <= K; K--) {
                            if (DPArr[I, J, K].HasValue == false) {
                                continue;
                            }

                            Action<int, int, int, long> UpdateAct = (pNewI, pNewJ, pNewK, pNewVal) =>
                            {
                                if (DPArr[pNewI, pNewJ, pNewK].HasValue) {
                                    if (DPArr[pNewI, pNewJ, pNewK].Value <= pNewVal) {
                                        return;
                                    }
                                }
                                DPArr[pNewI, pNewJ, pNewK] = pNewVal;
                            };

                            // RとBでペアを作る場合
                            if (I == 0 && K <= 1) {
                                long MinDiff = ExecNibunhou_MinDiff(EachEvenVal, RValArr);
                                long NewVal = DPArr[I, J, K].Value + MinDiff;
                                UpdateAct(I + 1, J, K + 1, NewVal);
                            }

                            // GとBでペアを作る場合
                            if (J == 0 && K <= 1) {
                                long MinDiff = ExecNibunhou_MinDiff(EachEvenVal, GValArr);
                                long NewVal = DPArr[I, J, K].Value + MinDiff;
                                UpdateAct(I, J + 1, K + 1, NewVal);
                            }
                        }
                    }
                }
            }
            AnswerKouhoList.Add(DPArr[1, 1, 2].Value);
        }
        return AnswerKouhoList.Min();
    }

    // 二分法で、Valとの差の最小値を返す
    static long ExecNibunhou_MinDiff(long pVal, long[] pArr)
    {
        var MinKouhoList = new List<long>();

        int Ind1 = ExecNibunhou_LowerBound(pVal, pArr);
        if (Ind1 > -1) {
            MinKouhoList.Add(Math.Abs(pVal - pArr[Ind1]));
        }

        int Ind2 = ExecNibunhou_LowerOrEqual_Max(pVal, pArr);
        if (Ind2 > -1) {
            MinKouhoList.Add(Math.Abs(pVal - pArr[Ind2]));
        }

        return MinKouhoList.Min();
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pArr.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pArr[0]) {
            return 0;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pArr[0]) {
            return -1;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

最初に
RGBごとの件数を求めます。
3つとも偶数なら解は0になります。

3つとも偶数でない場合で、和が偶数になるのは、
2つが奇数で、もう1つが偶数の時になります。

R G B
R G B
R G B
R G B
R G
といった図で考えると
(R,G)を作るか
(R,B)と(G,B)を作るか
の2つの解候補が考えられます。

(R,G)を作る場合は、RとGをごちゃ混ぜにして値の昇順にソートし、
前後で色が違う箇所の値の差が、解候補になります。

(R,B)と(G,B)を作る時の最適解は、
最小値[Rの数,Gの数,Bの数]を更新するDPで求まります。