ABC250-E Prefix Equality

問題へのリンク

C#のソース(DPで解く方法)

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("5");
            WillReturn.Add("1 2 3 4 5");
            WillReturn.Add("1 2 2 4 3");
            WillReturn.Add("7");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 3");
            WillReturn.Add("4 4");
            WillReturn.Add("4 5");
            WillReturn.Add("5 5");
            //Yes
            //Yes
            //Yes
            //No
            //No
            //Yes
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int[] BArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int UB = AArr.GetUpperBound(0);

        // Aで最初に登場した添字[値]なDict
        var AppearIndDictA = new Dictionary<int, int>();

        // Bで最初に登場した添字[値]なDict
        var AppearIndDictB = new Dictionary<int, int>();

        for (int I = 0; I <= UB; I++) {
            if (AppearIndDictB.ContainsKey(BArr[I]) == false) {
                AppearIndDictB[BArr[I]] = I;
            }
            if (AppearIndDictA.ContainsKey(AArr[I]) == false) {
                AppearIndDictA[AArr[I]] = I;
            }
        }

        // 集合が等しくなるBの最小Ind[AのInd]
        int[] DPArr1 = new int[UB + 1];

        // 集合が等しくなるAの最小Ind[BのInd]
        int[] DPArr2 = new int[UB + 1];

        for (int I = 0; I <= UB; I++) {
            int CurrA = AArr[I];
            var KouhoList = new List<int>();

            if (I > 0) {
                KouhoList.Add(DPArr1[I - 1]);
            }
            if (AppearIndDictB.ContainsKey(CurrA)) {
                KouhoList.Add(AppearIndDictB[CurrA]);
            }
            else {
                KouhoList.Add(int.MaxValue);
            }
            DPArr1[I] = KouhoList.Max();
        }

        for (int I = 0; I <= UB; I++) {
            int CurrB = BArr[I];
            var KouhoList = new List<int>();

            if (I > 0) {
                KouhoList.Add(DPArr2[I - 1]);
            }
            if (AppearIndDictA.ContainsKey(CurrB)) {
                KouhoList.Add(AppearIndDictA[CurrB]);
            }
            else {
                KouhoList.Add(int.MaxValue);
            }
            DPArr2[I] = KouhoList.Max();
        }

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(4)) {
            SplitAct(EachStr);
            int X = wkArr[0] - 1;
            int Y = wkArr[1] - 1;

            // 互いに包含関係なら集合として等しい
            if (DPArr1[X] <= Y && DPArr2[Y] <= X) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }
}

C#のソース(Zobrist Hashを使う方法)

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("5");
            WillReturn.Add("1 2 3 4 5");
            WillReturn.Add("1 2 2 4 3");
            WillReturn.Add("7");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 3");
            WillReturn.Add("4 4");
            WillReturn.Add("4 5");
            WillReturn.Add("5 5");
            //Yes
            //Yes
            //Yes
            //No
            //No
            //Yes
            //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();

        long UB = AArr.GetUpperBound(0);

        long[] AHashArr = new long[UB + 1];
        long[] BHashArr = new long[UB + 1];

        var InsZobristHash = new ZobristHash();
        var CurrSet = new HashSet<long>();
        for (long I = 0; I <= UB; I++) {
            if (CurrSet.Add(AArr[I])) {
                InsZobristHash.AddVal(AArr[I]);
            }
            AHashArr[I] = InsZobristHash.GetCurrHash();
        }

        // クリア処理
        CurrSet.Clear();
        InsZobristHash.ClearHash();

        for (long I = 0; I <= UB; I++) {
            if (CurrSet.Add(BArr[I]) ) {
                InsZobristHash.AddVal(BArr[I]);
            }
            BHashArr[I] = InsZobristHash.GetCurrHash();
        }

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(4)) {
            SplitAct(EachStr);
            long X = wkArr[0] - 1;
            long Y = wkArr[1] - 1;

            if (AHashArr[X] == BHashArr[Y]) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }
}

#region ZobristHash
internal class ZobristHash
{
    private long mCurrHash = 0;
    private Random mInsRandom = new Random();
    private Dictionary<long, long> mRandDict = new Dictionary<long, long>();

    // 現在のハッシュ値を返す
    internal long GetCurrHash()
    {
        return mCurrHash;
    }

    // ハッシュ値をクリア
    internal void ClearHash()
    {
        mCurrHash = 0;
    }

    // 状態を追加する
    internal void AddVal(long pAddVal)
    {
        if (mRandDict.ContainsKey(pAddVal) == false) {
            mRandDict[pAddVal] = mInsRandom.Next();
            mRandDict[pAddVal] <<= 32;
            mRandDict[pAddVal] += mInsRandom.Next();
        }
        mCurrHash ^= mRandDict[pAddVal];
    }
}
#endregion

解説

Zobrist Hashのやり方は、
1. 各要素について乱数を割り当てる
2. ハッシュ値は、含まれる要素の乱数の全てのXOR
となります。