ARC154-B New Place

問題へのリンク

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("4");
            WillReturn.Add("abab");
            WillReturn.Add("abba");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("arc");
            WillReturn.Add("cra");
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        string T = InputList[2];
        int Result = Solve1(S, T);
        Console.WriteLine(Result);
    }

    static int Solve1(string pS, string pT)
    {
        char[] SArr = pS.ToCharArray();
        char[] TArr = pT.ToCharArray();
        Array.Sort(SArr);
        Array.Sort(TArr);

        if (SArr.SequenceEqual(TArr) == false) {
            return -1;
        }

        if (pS == pT) {
            return 0;
        }

        int L = 0;
        int R = TArr.Length - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            string TailStr = pS.Substring(Mid);
            if (IsSubSequence(TailStr, pT)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 文字列Substrが、文字列LongStrの(連続してなくてもよい)部分列かを判定
    static bool IsSubSequence(string pSubstr, string pLongStr)
    {
        if (pSubstr == "") return true;

        int IndS = 0;
        int IndT = 0;

        int UB_S = pSubstr.Length - 1;
        int UB_T = pLongStr.Length - 1;

        while (true) {
            if (pSubstr[IndS] == pLongStr[IndT]) {
                IndS++;
                IndT++;
                if (IndS > UB_S) return true;
                if (IndT > UB_T) return false;
            }
            else {
                IndT++;
                if (IndT > UB_T) return false;
            }
        }
    }
}

解説

まず、SとTの文字列のマルチセットとみて
集合が不一致なら不可です。

次に、Sがabcdefだとして考察します。
先頭3文字を移動させる場合は、
defに、abcを自由に入れれると考えることができます。

すると、先頭何文字を消せば、
残った文字列が、Tの(連続してなくてもよい)部分列かの判定にできるかの判定となり、
単調性があるので二分探索できます。