ARC010-C 積み上げパズル

問題へのリンク

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 3 3 5");
            WillReturn.Add("R 1");
            WillReturn.Add("G 1");
            WillReturn.Add("B 1");
            WillReturn.Add("RGBRR");
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3 3 5");
            WillReturn.Add("R 1");
            WillReturn.Add("G 3");
            WillReturn.Add("B 2");
            WillReturn.Add("RBR");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 3 5 3");
            WillReturn.Add("R 1");
            WillReturn.Add("G 1");
            WillReturn.Add("B 1");
            WillReturn.Add("RRGRRBRR");
            //31
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 3 5 3");
            WillReturn.Add("R 1");
            WillReturn.Add("G 100");
            WillReturn.Add("B 1");
            WillReturn.Add("RRGRRBRR");
            //126
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int n = wkArr[0];
        int m = wkArr[1];
        int Y = wkArr[2];
        int Z = wkArr[3];

        // ボーナス[色]なDict
        var ColorBonusDict = new Dictionary<char, int>();
        foreach (string EachStr in InputList.Skip(1).Take(m)) {
            string[] SplitArr = EachStr.Split(' ');
            char Color = SplitArr[0][0];
            int Bonus = int.Parse(SplitArr[1]);
            ColorBonusDict[Color] = Bonus;
        }
        string BStr = InputList[m + 1];

        // Bit[色]なDict
        var ColorBitDict = new Dictionary<char, int>();
        char[] DistinctCharArr = BStr.ToCharArray().Distinct().ToArray();
        Array.Sort(DistinctCharArr);
        for (int I = 0; I <= DistinctCharArr.GetUpperBound(0); I++) {
            ColorBitDict[DistinctCharArr[I]] = (1 << I);
        }

        // 全色揃ったかの判定用
        int CompleteVal = (1 << m) - 1;

        // 最大得点[直前に置いた色,使用した色]なDP表
        int?[,] PrevDP = new int?[26 + 1, CompleteVal + 1];
        PrevDP[26, 0] = 0;

        foreach (char EachB in BStr) {
            int?[,] CurrDP = (int?[,])PrevDP.Clone();
            for (int I = 0; I <= 26; I++) {
                for (int J = 0; J <= CompleteVal; J++) {
                    if (PrevDP[I, J].HasValue == false) continue;

                    int NewI = EachB - 'A';
                    int NewJ = J | ColorBitDict[EachB];
                    int NewVal = PrevDP[I, J].Value;

                    // 色ボーナス
                    NewVal += ColorBonusDict[EachB];

                    // コンボボーナス
                    if (NewI == I) {
                        NewVal += Y;
                    }

                    // 全色ボーナス
                    if (J < CompleteVal && NewJ == CompleteVal) {
                        NewVal += Z;
                    }

                    if (CurrDP[NewI, NewJ].HasValue) {
                        if (NewVal <= CurrDP[NewI, NewJ].Value) {
                            continue;
                        }
                    }
                    CurrDP[NewI, NewJ] = NewVal;
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Cast<int?>().Max());
    }
}

解説

最大得点[直前に置いた色,使用した色]を更新するDPで解いてます。