ABC475-D Alphametic Prime

問題へのリンク

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("motor");
            //10607
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("byebye");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("coconut");
            //1010237
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static string mS;
    static char[] mCharArr;

    static long[] mSosuuArr;

    static string mGoalHash;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mS = InputList[0];
        mCharArr = mS.ToCharArray();

        var IndDict = new Dictionary<char, List<long>>();

        for (long I = 0; I <= mCharArr.GetUpperBound(0); I++) {
            char CurrChar = mCharArr[I];
            if (IndDict.ContainsKey(CurrChar) == false) {
                IndDict[CurrChar] = new List<long>();
            }
            IndDict[CurrChar].Add(I);
        }
        mGoalHash = GetHash(IndDict);

        Eratosthenes(9999999);

        foreach (long EachSosuu in mSosuuArr) {
            if (IsOK(EachSosuu)) {
                Console.WriteLine(EachSosuu);
                return;
            }
        }
        Console.WriteLine(-1);
    }

    static bool IsOK(long pVal)
    {
        if (GetLongKeta(pVal) != mS.Length) {
            return false;
        }

        char[] CharArr = pVal.ToString().ToCharArray();
        var wkIndDict = new Dictionary<char, List<long>>();

        for (long I = 0; I <= CharArr.GetUpperBound(0); I++) {
            char CurrChar = CharArr[I];
            if (wkIndDict.ContainsKey(CurrChar) == false) {
                wkIndDict[CurrChar] = new List<long>();
            }
            wkIndDict[CurrChar].Add(I);
        }
        string CurrHash = GetHash(wkIndDict);

        if (CurrHash == mGoalHash) {
            return true;
        }
        return false;
    }

    // 同じ文字の配置のハッシュ値を求める
    static string GetHash(Dictionary<char, List<long>> pDict)
    {
        var StrList = new List<string>();
        foreach (List<long> EachList in pDict.Values) {
            StrList.Add(LongEnumJoin("-", EachList));
        }
        StrList.Sort();

        var sb = new System.Text.StringBuilder();
        StrList.ForEach(pX =>
        {
            sb.Append(pX);
            sb.Append(',');
        });
        return sb.ToString();
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

    // エラトステネスの篩
    static void Eratosthenes(long pJyougen)
    {
        bool[] IsSosuuArr = new bool[pJyougen + 1];
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) {
                for (int J = I * 2; J <= IsSosuuArr.GetUpperBound(0); J += I) {
                    IsSosuuArr[J] = false;
                }
            }
        }

        var SosuuList = new List<long>();
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }

        mSosuuArr = SosuuList.ToArray();
    }

    ////////////////////////////////////////////////////////////////
    // long型の桁数を返す
    ////////////////////////////////////////////////////////////////
    static long GetLongKeta(long pVal)
    {
        if (pVal <= 9) return 1;
        if (pVal <= 99) return 2;
        if (pVal <= 999) return 3;
        if (pVal <= 9999) return 4;
        if (pVal <= 99999) return 5;
        if (pVal <= 999999) return 6;
        if (pVal <= 9999999) return 7;
        if (pVal <= 99999999) return 8;
        if (pVal <= 999999999) return 9;
        if (pVal <= 9999999999) return 10;
        if (pVal <= 99999999999) return 11;
        if (pVal <= 999999999999) return 12;
        if (pVal <= 9999999999999) return 13;
        if (pVal <= 99999999999999) return 14;
        if (pVal <= 999999999999999) return 15;
        if (pVal <= 9999999999999999) return 16;
        if (pVal <= 99999999999999999) return 17;
        if (pVal <= 999999999999999999) return 18;
        return 19;
    }
}

解説

1234567
ABABACD

は、同じ文字のIndをまとめて表現すると
1-3-5
2-4
6
7
と表現できます。
これは、昇順にソートしてから、カンマで区切りとすれば、
1-3-5,2-4,6,7,
となり、これをハッシュ値として、文字の一致場所が同じかを判定できます。

あとは、エラトステエネスの篩で素数列挙すれば解けます。