ABC-047-C 一次元リバーシ

■■■問題■■■

きつねの次郎と三郎が一次元リバーシで遊んでいます。
一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、
列の右端か左端に新たに石を打っていきます。

通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、
挟まれた黒の石は白い石に変わります。

ゲームの途中で三郎に急用ができて帰ってしまうことになりました。
このとき、盤面の状態は文字列Sで表されます。
石は |S| (文字列の長さ) 個並んでおり、
左から i (1 <= i <= |S|) 個目の石の色は、Sのi文字目がBのとき黒、Wのとき白です。

次郎は現在の盤面に対して、
できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。
最小で何個の石を打てばよいかを求めてください。

■■■入力■■■

S

●1 <= |S| <= 10万
●S に含まれる文字はBまたはWのいずれかである

■■■出力■■■

全ての石を同じ色にするために打つ必要のある石の個数の最小値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("BBBWW");
            //1
            //たとえば右端に黒い石を打つとすべての白い石を黒い石にすることができます。
            //他にも、左端に白い石を打つことでもすべての石の色を同じにできます。
            //いずれの場合も1個の石ですべての石を同じ色にすることができるので、1を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("WWWWWW");
            //0
            //最初から全ての石が同じ色の場合、新たに石を打つ必要はありません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("WBWBWBWBWB");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        int Cnt = 0;
        char CurrSeqChar = '\0';
        foreach (char EachChar in S) {
            if (CurrSeqChar != EachChar) {
                Cnt++;
                CurrSeqChar = EachChar;
            }
        }
        Console.WriteLine(Cnt - 1);
    }
}

解説

連続したBおよびWは、単独のBおよびWと考えることができます。

 BWBWBで左にWを置くと、
WWWBWBとなり、
連続したWを単独のWに変換すると
  WBWBとなり、これは、結局、先頭のBを削除した結果となります。

以上により、連続したWおよびBを単独のWおよびBとした際の、
(文字数-1)が解となります。