ARC195-A Twice Subsequence

問題へのリンク

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 2");
            WillReturn.Add("1 2 1 2");
            WillReturn.Add("1 2");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 2 1");
            WillReturn.Add("1 2");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 1 2");
            WillReturn.Add("2 1");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }
    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] BArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        string Result = Solve(AArr, BArr);
        Console.WriteLine(Result);
    }

    static string Solve(long[] pAArr, long[] pBArr)
    {
        var SeiIndSet = new HashSet<long>();
        long CurrAInd1 = 0;

        foreach (long EachB in pBArr) {
            while (CurrAInd1 <= pAArr.GetUpperBound(0)) {
                if (pAArr[CurrAInd1] == EachB) {
                    SeiIndSet.Add(CurrAInd1++);
                    break;
                }
                CurrAInd1++;
            }
        }

        if (SeiIndSet.Count < pBArr.Length) {
            return "No";
        }

        var RevIndSet = new HashSet<long>();
        long CurrAInd2 = pAArr.GetUpperBound(0);
        foreach (long EachB in pBArr.Reverse()) {
            while (0 <= CurrAInd2) {
                if (pAArr[CurrAInd2] == EachB) {
                    RevIndSet.Add(CurrAInd2--);
                    break;
                }
                CurrAInd2--;
            }
        }

        if (SeiIndSet.SetEquals(RevIndSet)) {
            return "No";
        }
        return "Yes";
    }
}

解説

前から貪欲と
後ろから貪欲で
使用したIndexの集合が等しいかを判定してます。