ARC166-A Replace C or Swap AB

問題へのリンク

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");
            WillReturn.Add("3 ABC ABC");
            WillReturn.Add("1 C B");
            WillReturn.Add("1 B C");
            WillReturn.Add("2 AB BA");
            WillReturn.Add("2 BA AB");
            WillReturn.Add("3 CCB ABA");
            //Yes
            //Yes
            //No
            //Yes
            //No
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("5 ABABA BABAB");
            WillReturn.Add("5 ABCBC BBABA");
            WillReturn.Add("5 CCCCC CBABC");
            WillReturn.Add("5 BBAAA AAABB");
            WillReturn.Add("5 AAABB BBAAA");
            WillReturn.Add("5 ACACB BAACB");
            WillReturn.Add("5 ACACB BBACA");
            //No
            //Yes
            //Yes
            //No
            //Yes
            //Yes
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');
            string X = SplitArr[1];
            string Y = SplitArr[2];
            bool Result = Solve(X, Y);
            //Console.WriteLine("{0}と{1}は{2}", X, Y, Result);
            if (Result) sb.AppendLine("Yes");
            else sb.AppendLine("No");
        }
        Console.Write(sb.ToString());
    }

    struct CheckDef
    {
        internal string XStr;
        internal string YStr;
    }
    static List<CheckDef> mCheckList = new List<CheckDef>();

    static bool Solve(string pX, string pY)
    {
        int UB = pX.Length - 1;

        // 必要条件のチェック
        for (int I = 0; I <= UB; I++) {
            if (pY[I] == 'C' && pX[I] != 'C') {
                return false;
            }
        }

        mCheckList.Clear();

        var sb1 = new System.Text.StringBuilder();
        var sb2 = new System.Text.StringBuilder();

        Action AddAct = () =>
        {
            if (sb1.Length > 0) {
                CheckDef WillAdd;
                WillAdd.XStr = sb1.ToString();
                WillAdd.YStr = sb2.ToString();
                mCheckList.Add(WillAdd);

                sb1.Length = sb2.Length = 0;
            }
        };

        for (int I = 0; I <= UB; I++) {
            if (pX[I] == 'C' && pY[I] == 'C') {
                AddAct();
                continue;
            }
            sb1.Append(pX[I]);
            sb2.Append(pY[I]);
            if (I == UB) {
                AddAct();
            }
        }

        foreach (CheckDef EachCheck in mCheckList) {
            //Console.WriteLine("X={0},Y={1}", EachCheck.XStr, EachCheck.YStr);
            bool Result = IsOK(EachCheck.XStr, EachCheck.YStr);
            if (Result == false) return false;
        }

        return true;
    }

    static bool IsOK(string pStrX, string pStrY)
    {
        int XACnt = pStrX.ToCharArray().Count(pX => pX == 'A');
        int XBCnt = pStrX.ToCharArray().Count(pX => pX == 'B');

        int YACnt = pStrY.ToCharArray().Count(pX => pX == 'A');
        int YBCnt = pStrY.ToCharArray().Count(pX => pX == 'B');

        if (XACnt > YACnt) return false;
        if (XBCnt > YBCnt) return false;

        char[] CharArr = pStrX.ToCharArray();

        // CをAからBに変換する。
        // XとYで、AとBの総数一致は必要条件であり、
        // Bは右から借りてこれるので、なるべくBを右側にする
        int UB = CharArr.GetUpperBound(0);
        for (int I = 0; I <= UB; I++) {
            if (CharArr[I] == 'C') {
                if (XACnt < YACnt) {
                    CharArr[I] = 'A';
                    XACnt++;
                }
                else {
                    CharArr[I] = 'B';
                    XBCnt++;
                }
            }
        }

        //Console.WriteLine("Cを変換後のX={0}", new string(CharArr));

        // Bの位置はキューで管理する
        var Que = new Queue<int>();
        for (int I = 0; I <= UB; I++) {
            if (CharArr[I] == 'B') {
                Que.Enqueue(I);
            }
        }

        for (int I = 0; I <= UB; I++) {
            if (CharArr[I] == pStrY[I]) {
                continue;
            }

            if (CharArr[I] == 'B' && pStrY[I] == 'A') {
                return false;
            }

            if (CharArr[I] == 'A' && pStrY[I] == 'B') {
                bool IsOK = false;
                while (Que.Count > 0) {
                    int Dequeued = Que.Dequeue();
                    if (Dequeued < I) continue;

                    CharArr[I] = 'B';
                    CharArr[Dequeued] = 'A';
                    IsOK = true;
                    break;
                }
                if (IsOK == false) return false;
            }
        }
        return true;
    }
}

解説

文字Xも文字YもCの箇所で、分割して考えることができます。
(文字YがCなのに、文字XがCでない場合は、不一致が確定します)

ABABCAACABC
BABACBBCBAC

次に文字XのCを、AからBに変換することを考えます。
ABをBAに変換できるということは、
AAABをBAAAに変換できるということでもあるので
「文字Xは、Bを右から借りてくることができる」と考えます。

なので、文字XのCは、
左から順にAを優先して設定します。
(文字YのAとBの個数は、事前に数えておきます)

これで、文字Xも文字Yも
AとBだけで考えればよくなったので、
後は、文字Xを左から走査し、
Yに合わせていけば良いです。