using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("1 10"); WillReturn.Add("RRRRRRRRRRWWWWWWWWWWBBBBBBBBBB"); //21 //Rの1個となりがRであってはならないのでRを9個抜く。 //Bの10個となりにBがあることは無いのでBは抜かなくてよい。 //最終的には RWWWWWWWWWWBBBBBBBBBB が残る。 } else if (InputPattern == "Input2") { WillReturn.Add("1 2"); WillReturn.Add("WRWWBBRRRWWBBRRRRWWWBBBRRWWBBB"); //22 } else if (InputPattern == "Input3") { WillReturn.Add("7 11"); WillReturn.Add("BWBWRWRRWBRRWRRWWBBBRRWBBRWBBW"); //27 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { var sw = System.Diagnostics.Stopwatch.StartNew(); List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray(); int Kr = wkArr[0]; int Kb = wkArr[1]; string S = InputList[1]; Console.WriteLine(ExecDFS(S, Kr, Kb)); } struct JyoutaiDef { internal int CurrP; internal string CurrStr; internal int RemoveCnt; } //2の20乗通りの順列を列挙 static int ExecDFS(string pS, int pKr, int pKb) { var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrP = 0; WillPush.CurrStr = ""; WillPush.RemoveCnt = 0; stk.Push(WillPush); int AnswerRemoveCnt = int.MaxValue; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //クリア判定 if (Popped.CurrP > pS.Length - 1) { if (IsOK(Popped.CurrStr, pKr, pKb)) { if (AnswerRemoveCnt > Popped.RemoveCnt) { AnswerRemoveCnt = Popped.RemoveCnt; } } continue; } Action PushSyori = pAddStr => { WillPush.CurrP = Popped.CurrP + 1; WillPush.CurrStr = Popped.CurrStr + pAddStr; WillPush.RemoveCnt = Popped.RemoveCnt; if (pAddStr.Length == 0) WillPush.RemoveCnt++; //下限値枝切り if (AnswerRemoveCnt <= WillPush.RemoveCnt) return; stk.Push(WillPush); }; if (pS[Popped.CurrP] == 'B') { PushSyori("B"); PushSyori(""); } if (pS[Popped.CurrP] == 'R') { PushSyori("R"); PushSyori(""); } if (pS[Popped.CurrP] == 'W') { PushSyori("W"); } } return pS.Length - AnswerRemoveCnt; } //OKなレンガの配置かを判定 static bool IsOK(string pS, int pKr, int pKb) { int UB = pS.Length - 1; for (int I = 0; I <= UB; I++) { if (pS[I] == 'R' && I + pKr <= UB && pS[I + pKr] == 'R') return false; if (pS[I] == 'B' && I + pKb <= UB && pS[I + pKb] == 'B') return false; } return true; } }