ABC329-E Stamp

問題へのリンク

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("7 3");
            WillReturn.Add("ABCBABC");
            WillReturn.Add("ABC");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 3");
            WillReturn.Add("ABBCABC");
            WillReturn.Add("ABC");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("12 2");
            WillReturn.Add("XYXXYXXYYYXY");
            WillReturn.Add("XY");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] GoalCharArr = InputList[1].ToArray();
        int UB1 = GoalCharArr.GetUpperBound(0);

        char[] StampCharArr = InputList[2].ToArray();
        int UB2 = StampCharArr.GetUpperBound(0);

        var Que = new Queue<int>();
        for (int I = 0; I <= UB1; I++) {
            Que.Enqueue(I);
        }

        while (Que.Count > 0) {
            int Deququed = Que.Dequeue();

            if (Deququed + UB2 > UB1) continue;

            bool IsOK = true;
            for (int I = 0; I <= UB2; I++) {
                int TargetInd = Deququed + I;

                if (GoalCharArr[TargetInd] == '*') continue;
                if (GoalCharArr[TargetInd] == StampCharArr[I]) continue;

                IsOK = false;
            }

            if (IsOK == false) continue;

            bool WillEnqueue = false;
            for (int I = 0; I <= UB2; I++) {
                int TargetInd = Deququed + I;
                if (GoalCharArr[TargetInd] != '*') {
                    GoalCharArr[TargetInd] = '*';
                    WillEnqueue = true;
                }
            }

            if (WillEnqueue) {
                for (int I = Deququed - StampCharArr.Length; I < Deququed + StampCharArr.Length; I++) {
                    if (0 <= I && I <= UB1) {
                        Que.Enqueue(I);
                    }
                }
            }
        }

        if (Array.TrueForAll(GoalCharArr, pX => pX == '*')) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }
}

解説

スタンプがABCの場合で考察します。

ABCBABCという文字列は、最終形そのものなので十分条件となります。

*をワイルドカードとして、
ABCを***に変更した
***B***も、十分条件であります。

*B*とスタンプがABCであることふまえて
*******も、十分条件であります。

このように十分条件を求めていき、解くことができます。