トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

No.559 swapAB列

■■■問題■■■

文字Aと文字Bからなる文字列がある。
文字列に対して次のような操作が認められている。

●1回の操作で隣り合う文字を入れ替える。

全ての文字Aを左に、文字Bを右に寄せるには最低何回の操作が必要か。

■■■入力■■■

S

●Sは文字Aと文字Bからなる文字列
●1 <= 文字列Sの長さ <= 12

■■■出力■■■

答えを出力してください。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("BA");
            //1
            //BAを1回の操作で入れ替えてABにすることができます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("B");
            //0
            //文字列は1文字の場合もあります。
            //また、この場合文字Bはこれ以上右に行かないので右に寄っているとみなします。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("ABAABA");
            //4
            //「ABAABA」→「ABAAAB」→「AABAAB」→「AAABAB」→「AAAABB」。
            //例えばこのような手順で最低4回の操作が必要です。
        }
        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 Answer = 0;
        while (true) {
            int wkInd = S.IndexOf("BA");
            if (wkInd == -1) break;

            S = S.Remove(wkInd, 2);
            S = S.Insert(wkInd, "AB");
            Answer++;
        }
        Console.WriteLine(Answer);
    }
}


解説

文字列の左からBAという文字列を検索し、
見つけたらABに置換することを繰り返してます。