ABC140-D Face Produces Unhappiness

問題へのリンク

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 1");
            WillReturn.Add("LRLRRL");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("13 3");
            WillReturn.Add("LRRLRLRRLRLLR");
            //9
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 1");
            WillReturn.Add("LLLLLRRRRR");
            //9
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("9 2");
            WillReturn.Add("RRRLRLRLL");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    // ランレングス圧縮情報をListで管理
    struct RunLenInfo
    {
        internal bool IsLeft;
        internal int RunLen;
    }
    static List<RunLenInfo> mRunLenList = new List<RunLenInfo>();

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mK = wkArr[1];

        string S = InputList[1];

        // ランレングス圧縮を行う
        int StrUB = S.Length - 1;
        char PrevChar = S[0];
        int StrLen = 0;
        for (int I = 0; I <= StrUB; I++) {
            if (S[I] != PrevChar) {
                RunLenInfo WillAdd;
                WillAdd.IsLeft = (PrevChar == 'L');
                WillAdd.RunLen = StrLen;
                mRunLenList.Add(WillAdd);
                StrLen = 0;
                PrevChar = S[I];
            }
            StrLen++;

            if (I == StrUB) {
                RunLenInfo WillAdd;
                WillAdd.IsLeft = (S[I] == 'L');
                WillAdd.RunLen = StrLen;
                mRunLenList.Add(WillAdd);
            }
        }

        // 文字が1通りしかない場合
        if (mRunLenList.Count == 1) {
            Console.WriteLine(mRunLenList[0].RunLen - 1);
            return;
        }

        //foreach(RunLenInfo EachRunLenInfo in mRunLenList){
        //    Console.WriteLine("IsLeft={0},RunLen={1}", EachRunLenInfo.IsLeft, EachRunLenInfo.RunLen);
        //}

        int ResultEven = SolveEven();
        int ResultOdd = SolveOdd();

        Console.WriteLine(Math.Max(ResultEven, ResultOdd));
    }

    // 全ての文字を、ランレングス圧縮した際の0番目(LかR)に揃えた時の得点を返す
    static int SolveEven()
    {
        int CurrScore = mRunLenList.Sum(pX => pX.RunLen - 1);

        int RunLenListUB = mRunLenList.Count - 1;
        int RestCnt = mK;

        // 0番目に合わせるので、奇数の添字を変更
        for (int I = 1; I <= RunLenListUB; I += 2) {
            if (I == RunLenListUB) {
                CurrScore++;
            }
            else {
                CurrScore += 2;
            }

            // K回までなのでBreak
            if (--RestCnt == 0) break;
        }
        return CurrScore;
    }

    // 全ての文字を、ランレングス圧縮した際の1番目(LかR)に揃えた時の得点を返す
    static int SolveOdd()
    {
        int CurrScore = mRunLenList.Sum(pX => pX.RunLen - 1);

        int RunLenListUB = mRunLenList.Count - 1;
        int RestCnt = mK;

        // 1番目に合わせるので、偶数の添字を変更
        for (int I = 2; I <= RunLenListUB; I += 2) {
            if (I == RunLenListUB) {
                CurrScore++;
            }
            else {
                CurrScore += 2;
            }

            // K回までなのでBreak
            if (--RestCnt == 0) break;
        }

        // 0番目の添字を変更
        if (RestCnt > 0) {
            CurrScore++;
        }
        return CurrScore;
    }
}

解説

RRRLLLRRLLL
をランレングス圧縮すると
R3L3R2L3
でランレングス圧縮した時の、
(数字-1)の総和
が得点と分かります。

ランレングス圧縮した時の
偶数番目と奇数番目のどっちかに揃えるかの
2通りを試してます。
ただし、端に隣接している番目は、試行の最後にする必要があります。