ARC172-C Election

問題へのリンク

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("AABB");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("AAAA");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("BBBAAABBAA");
            //5
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("172");
            WillReturn.Add("AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB");
            //24
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] CArr = InputList[1].ToCharArray();

        var ResultIntList1 = new List<int>();
        for (int I = 1; I <= CArr.GetUpperBound(0); I++) {
            int AddVal = CArr[I] == CArr[0] ? 1 : -1;

            if (ResultIntList1.Count > 0) {
                AddVal += ResultIntList1.Last();
            }
            ResultIntList1.Add(AddVal);
        }
        int UB = ResultIntList1.Count - 1;

        var ResultIntList2 = new List<int>();
        ResultIntList1.ForEach(pX => ResultIntList2.Add(pX + 1));

        var sb1 = new System.Text.StringBuilder();
        ResultIntList1.ForEach(pX => sb1.Append(DeriveSign(pX)));

        var sb2 = new System.Text.StringBuilder();
        ResultIntList2.ForEach(pX => sb2.Append(DeriveSign(pX)));

        var InsRollingHash1 = new RollingHash(sb1.ToString());
        var InsRollingHash2 = new RollingHash(sb2.ToString());

        var RollingHashSet = new HashSet<decimal>();

        for (int I = 0; I <= UB; I++) {
            // 後ろに追加
            int CurrCnt = ResultIntList1[I] + 1;

            decimal PrevHash = InsRollingHash1.GetRangeHash(0, I);
            var InsRollingHashUtil1 = new RollingHashUtil(PrevHash, I + 1);

            string MidStr = DeriveSign(CurrCnt).ToString();
            InsRollingHashUtil1.AddRightStr(MidStr);

            decimal NextHash = 0;
            if (I < UB) {
                NextHash = InsRollingHash2.GetRangeHash(I + 1, UB);
                InsRollingHashUtil1.AddRightHash(NextHash, UB - I);
            }

            RollingHashSet.Add(InsRollingHashUtil1.GetRollingHash());
        }

        // 前に追加
        decimal wkHash = InsRollingHash2.GetRangeHash(0, UB);
        var InsRollingHashUtil2 = new RollingHashUtil(wkHash, UB + 1);
        InsRollingHashUtil2.AddLeftStr("+");
        decimal AddHash = InsRollingHashUtil2.GetRollingHash();
        RollingHashSet.Add(AddHash);

        Console.WriteLine(RollingHashSet.Count);
    }

    // 数値を引数として、符号を返す
    static char DeriveSign(int pVal)
    {
        if (pVal > 0) return '+';
        if (pVal < 0) return '-';
        return '0';
    }
}

#region RollingHash
// ローリングハッシュ
internal class RollingHash
{
    const decimal Base = 100M;
    const decimal Hou = 67280421310721M;

    // ハッシュ値[終了Ind]で、[0,終了Ind]のハッシュ値を保持
    internal decimal[] mHashArr;

    // 桁の重みの配列
    decimal[] mOmomiArr;

    string mBaseStr;

    long UB; // コンストラクタで渡した文字列のUB

    // コンストラクタ
    internal RollingHash(string pBaseStr)
    {
        mBaseStr = pBaseStr;

        decimal Omomi = 1;
        UB = pBaseStr.Length - 1;

        mHashArr = new decimal[UB + 1];
        mOmomiArr = new decimal[UB + 1];
        for (int I = 0; I <= UB; I++) {
            mOmomiArr[I] = Omomi;
            if (I > 0) {
                mHashArr[I] += mHashArr[I - 1] * Base;
                mHashArr[I] %= Hou;
            }
            mHashArr[I] += pBaseStr[I];
            mHashArr[I] %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }
    }

    // [Sta,End]のハッシュ値を返す
    internal decimal GetRangeHash(long pSta, long pEnd)
    {
        decimal WillReturn = mHashArr[pEnd];
        if (pSta > 0) {
            long Range = pEnd - pSta + 1;
            decimal PrevVal = mHashArr[pSta - 1];
            decimal MinusVal = PrevVal * mOmomiArr[Range];
            MinusVal %= Hou;
            WillReturn -= MinusVal;
            if (WillReturn < 0) {
                WillReturn += Hou;
            }
        }
        return WillReturn;
    }

    // 左の文字数、追加文字列を引数とし、
    // 間に文字列をInsertした時のハッシュ値を返す
    internal decimal GetInsertedHash(long pLeftCnt, string pInsertStr)
    {
        if (pLeftCnt > mBaseStr.Length) {
            throw new Exception("pLeftCntにmBaseStr.lengthより大きい値が指定されました。");
        }

        long RightCnt = mBaseStr.Length - pLeftCnt;

        // 重み配列が不足してたら、補完する
        if (mOmomiArr.GetUpperBound(0) < RightCnt) {
            decimal[] NewOmomiArr = new decimal[mOmomiArr.Length * 2];
            mOmomiArr.CopyTo(NewOmomiArr, 0);

            for (long I = mOmomiArr.GetUpperBound(0) + 1; I <= NewOmomiArr.GetUpperBound(0); I++) {
                decimal NewVal = NewOmomiArr[I - 1];
                NewVal *= Base;
                NewVal %= Hou;
                NewOmomiArr[I] = NewVal;
            }
            mOmomiArr = NewOmomiArr;
        }

        // 右のハッシュ値
        decimal HashRight = 0;
        if (RightCnt > 0) {
            HashRight = GetRangeHash(UB - RightCnt + 1, UB);
        }

        // 中央のハッシュ値
        decimal Omomi = mOmomiArr[RightCnt];
        decimal HashMid = 0;
        foreach (char EachChar in pInsertStr) {
            HashMid += Omomi * EachChar;
            HashMid %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }

        // 左のハッシュ値
        decimal HashLeft = 0;
        if (pLeftCnt > 0) {
            HashLeft = GetRangeHash(0, pLeftCnt - 1);

            // 重みを掛ける
            HashLeft *= Omomi;
            HashLeft %= Hou;
        }

        decimal Result = HashLeft;
        Result += HashMid;
        Result %= Hou;
        Result += HashRight;
        Result %= Hou;
        return Result;
    }
}
#endregion

#region RollingHashUtil
// ローリングハッシュのutilクラス
internal class RollingHashUtil
{
    const decimal Base = 100M;
    const decimal Hou = 67280421310721M;

    // 桁の重みの配列
    static decimal[] mOmomiArr = new decimal[0];

    int mStrLen;
    decimal mRollingHash;

    // コンストラクタ
    // Hash値と、長さを指定
    internal RollingHashUtil(decimal pRollingHash, int pStrLen)
    {
        mStrLen = pStrLen;
        mRollingHash = pRollingHash;

        if (mOmomiArr.Length < 16) {
            mOmomiArr = new decimal[16];
            decimal Omomi = 1;
            for (int I = 0; I <= mOmomiArr.GetUpperBound(0); I++) {
                mOmomiArr[I] = Omomi;
                Omomi *= Base;
                Omomi %= Hou;
            }
        }
    }

    // 桁の重みを返す
    // 引数が0なら、1をreturn
    // 引数が1なら、100をreturn
    // 引数が2なら、10000をreturn
    static private decimal GetOmomi(int pInd)
    {
        // 重み配列が不足してたら、補完する
        while (mOmomiArr.GetUpperBound(0) < pInd) {
            decimal[] NewOmomiArr = new decimal[mOmomiArr.Length * 2];
            mOmomiArr.CopyTo(NewOmomiArr, 0);

            for (long I = mOmomiArr.GetUpperBound(0) + 1; I <= NewOmomiArr.GetUpperBound(0); I++) {
                decimal NewVal = NewOmomiArr[I - 1];
                NewVal *= Base;
                NewVal %= Hou;
                NewOmomiArr[I] = NewVal;
            }
            mOmomiArr = NewOmomiArr;
        }
        return mOmomiArr[pInd];
    }

    // ハッシュ値を返す
    internal decimal GetRollingHash()
    {
        return mRollingHash;
    }

    // 文字列長を返す
    internal decimal GetStrLen()
    {
        return mStrLen;
    }

    // 文字列のハッシュ値を求める
    static decimal DeriveRollingHash(string pTargetStr)
    {
        decimal WillReturn = 0;
        decimal Omomi = 1;
        foreach (char EachChar in pTargetStr) {
            WillReturn += Omomi * EachChar;
            WillReturn %= Hou;

            Omomi *= Base;
            Omomi %= Hou;
        }
        return WillReturn;
    }

    // 左に文字列を追加(string指定)
    internal void AddLeftStr(string pLeftStr)
    {
        decimal LeftRollingHash = DeriveRollingHash(pLeftStr);
        decimal Omomi = GetOmomi(mStrLen);
        LeftRollingHash *= Omomi;
        LeftRollingHash %= Hou;

        mRollingHash += LeftRollingHash;
        mRollingHash %= Hou;

        mStrLen += pLeftStr.Length;
    }

    // 左に文字列を追加(Hash値と、長さを指定)
    internal void AddLeftHash(decimal pLeftRollingHash, int pLeftLen)
    {
        decimal Omomi = GetOmomi(mStrLen);
        pLeftRollingHash *= Omomi;
        pLeftRollingHash %= Hou;

        mRollingHash += pLeftRollingHash;
        mRollingHash %= Hou;

        mStrLen += pLeftLen;
    }

    // 右に文字列を追加(string指定)
    internal void AddRightStr(string pRightStr)
    {
        decimal RightRollingHash = DeriveRollingHash(pRightStr);
        decimal Omomi = GetOmomi(pRightStr.Length);
        mRollingHash *= Omomi;
        mRollingHash %= Hou;

        mRollingHash += RightRollingHash;
        mRollingHash %= Hou;

        mStrLen += pRightStr.Length;
    }

    // 右に文字列を追加(Hash値と、長さを指定)
    internal void AddRightHash(decimal pRightRollingHash, int pRightLen)
    {
        decimal Omomi = GetOmomi(pRightLen);
        mRollingHash *= Omomi;
        mRollingHash %= Hou;

        mRollingHash += pRightRollingHash;
        mRollingHash %= Hou;

        mStrLen += pRightLen;
    }
}
#endregion

解説

1番目の人が自分自身に投票したと考えて
1番目の人の選挙情勢発表だと考えることができます。

1番目の人の分を開票することは、
後続の結果全てに+1されると考えれば、
最初から+1した結果の文字列と
+1してない文字列の
ローリングハッシュを組み合わせて解けると分かります。