Tenka1 Programmer Beginner Contest 2019 C Stones

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        S = S.Replace('.', 'W');
        S = S.Replace('#', 'B');

        // 変更回数の最小値[現在の石]なDP表
        var PrevDP = new SortedDictionary<char, int>();
        PrevDP['\0'] = 0;

        foreach (char EachStone in S) {
            var CurrDP = new SortedDictionary<char, int>();
            foreach (var EachPair in PrevDP) {
                Action<char, int> UpdateAct = (pNewKey, pNewVal) =>
                {
                    // 前の文字が黒の場合は、次の文字を白にできない
                    if (EachPair.Key == 'B' && pNewKey == 'W') {
                        return;
                    }

                    if (CurrDP.ContainsKey(pNewKey)) {
                        if (CurrDP[pNewKey] <= pNewVal) {
                            return;
                        }
                    }
                    CurrDP[pNewKey] = pNewVal;
                };

                // 色を変える経路
                if (EachStone == 'B') {
                    UpdateAct('W', EachPair.Value + 1);
                }
                if (EachStone == 'W') {
                    UpdateAct('B', EachPair.Value + 1);
                }

                // 色を変えない経路
                UpdateAct(EachStone, EachPair.Value);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Values.Min());
    }
}

解説

変更回数の最小値[現在の石]を更新するDPで解いてます。