東工大プロコン2015 D 文字列と素数

■■■問題■■■

文字列Sが与えられる。以下の条件を満たす変換でSからある数への変換を行う。

●Sの各文字を1,3,5,7,9のいずれかの数字に変換する。
●同じ文字は同じ数字に、異なる文字は異なる数字に変換しなくてはならない。

上の条件を満たす変換によって、文字列Sを素数に変換することできるだろうか。

■■■入力■■■

S

●1行で文字列 S(1 <= |S| <= 10)が与えられる。
●Sの各文字は、英小文字である。

■■■出力■■■

素数の変換先を得られる場合は、そのような素数を1つ出力してください。
素数の変換先がない場合は、-1を出力してください。

素数の変換先が複数ある場合は、いずれを出力しても正解として扱われる。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("tit");
            //131
            //他にも、151,171,191,313,・・・ のいずれかを出力しても正解として扱われる
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("titech");
            //757319
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("tokyotech");
            //-1
            //文字の種類が多すぎるため、条件を満たす変換を構成することができません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        if (S.Distinct().Count() > 5) {
            Console.WriteLine(-1);
            return;
        }

        char[] NumArr = { '1', '3', '5', '7', '9' };

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrStr = S;
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            int wkInd = Array.FindLastIndex(Popped.CurrStr.ToCharArray(), X => X < '1' || '9' < X);

            //クリア判定
            if (wkInd == -1) {
                if (IsPrime(long.Parse(Popped.CurrStr))) {
                    Console.WriteLine(Popped.CurrStr);
                    return;
                }
                continue;
            }

            foreach (char EachChar in NumArr) {
                if (Popped.CurrStr.Contains(EachChar)) continue;

                //枝切り 2桁以上の数であれば、末尾に5は使えない
                if (S.Length >= 2 && wkInd == S.Length - 1 && EachChar == '5')
                    continue;

                char wkChar = Popped.CurrStr[wkInd];
                WillPush.CurrStr = Popped.CurrStr.Replace(wkChar, EachChar);
                stk.Push(WillPush);
            }
        }
        Console.WriteLine(-1);
    }

    //試し割りで素数かを判定
    static bool IsPrime(long pTarget)
    {
        if (pTarget == 2) return true;
        if (pTarget % 2 == 0) return false;
        for (long I = 3; I * I <= pTarget; I += 2) {
            if (pTarget % I == 0) return false;
        }
        return true;
    }
}

解説

1,3,5,7,9 で5!で120通りしかないうえに、
1桁目が5の場合を枝切りすれば、
4*4*3*2で96通りですので、DFSで全探索してます。