Problem170 連結された積が0から9を網羅する数の最大値

問題

6を1273と9854に掛けると,

6 × 1273 = 7638
6 × 9854 = 59124
となる.

これらの積をつなげることで, 1から9を網羅するパンデジタル数, 763859124を得る.
763859124を"6と(1273,9854)の連結された積"と呼ぶことにする.
元の数をつなげた 612739854も1から9を網羅する数であることに注意.

同じことが0から9を網羅する数にたいしてもできる.

元の数をつなげた数も0から9を網羅する数となるような,
ある整数と2つ以上の整数の連結された積が0から9を網羅する数の最大値を求めよ.

ソース

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

class Program
{
    const int UB = 9;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        string AnswerStr = new string('0', 10);

        foreach (string EachKouho in DeriveKouhoEnum()) {
            //Aは2桁まで
            for (int I = 0; I <= 1; I++) {
                string AStr = EachKouho.Substring(0, I + 1);
                int AInt = int.Parse(AStr);

                List<long> NumListA = DeriveNumList(AInt);

                //Mod9で枝切り
                long ModVal = AInt % 9;
                ModVal *= 2; //Aは2回使う
                for (long J = 0; J <= 9; J++) {
                    if (NumListA.Contains(J) == false)
                        ModVal += J % 9;
                }
                if (ModVal % 9 > 0) continue;

                for (int J = I + 1; J <= UB - 1; J++) {
                    string BStr = EachKouho.Substring(I + 1, J - I);
                    string CStr = EachKouho.Substring(J + 1);

                    //前ゼロは不許可
                    if (BStr.Length > 1 && BStr.StartsWith("0")) continue;
                    if (CStr.Length > 1 && CStr.StartsWith("0")) continue;

                    int BInt = int.Parse(BStr);
                    int CInt = int.Parse(CStr);

                    long DLong = (long)AInt * BInt;
                    long ELong = (long)AInt * CInt;

                    List<long> wkNumList = new List<long>();
                    wkNumList.AddRange(DeriveNumList(DLong));
                    wkNumList.AddRange(DeriveNumList(ELong));

                    if (wkNumList.Count != 10) continue;
                    if (wkNumList.GroupBy(X => X).Any(X => X.Count() > 1)) continue;

                    string CurrStr = string.Format("{0}{1}", DLong, ELong);
                    if (AnswerStr.CompareTo(CurrStr) < 0) {
                        AnswerStr = CurrStr;
                        Console.WriteLine("解候補を発見");
                        Console.WriteLine("{0}*{1}={2}", AInt, BInt, DLong);
                        Console.WriteLine("{0}*{1}={2}", AInt, CInt, ELong);
                        Console.WriteLine("連結積は{0}", CurrStr);
                        Console.WriteLine();
                    }
                }
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
    }

    //同じ数字を複数含まない10桁の数の列挙を返す
    static IEnumerable<string> DeriveKouhoEnum()
    {
        var KouhoList = new List<string>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (char I = '1'; I <= '9'; I++) {
            WillPush.CurrStr = I.ToString();
            Stk.Push(WillPush);
        }

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

            //クリア判定
            if (Popped.CurrStr.Length == 10) {
                yield return Popped.CurrStr;
                continue;
            }

            for (char I = '0'; I <= '9'; I++) {
                if (Popped.CurrStr.Contains(I))
                    continue;

                WillPush.CurrStr = Popped.CurrStr + I.ToString();
                Stk.Push(WillPush);
            }
        }
    }

    //数字のListを返す
    static List<long> DeriveNumList(long pTarget)
    {
        var WillReturn = new List<long>();

        long CopiedVal = pTarget;
        do {
            long ModVal = CopiedVal % 10;
            WillReturn.Add(ModVal);
            CopiedVal /= 10;
        } while (CopiedVal > 0);
        return WillReturn;
    }
}

実行結果

解候補を発見
9*87345=786105
9*1026=9234
連結積は7861059234

解候補を発見
9*1=9
9*87345026=786105234
連結積は9786105234

解候補を発見
27*36508=985716
27*149=4023
連結積は9857164023

経過時間=00:00:15.7157397

解説

A*B=D
A*C=E

とすると、
Aが5桁の場合、5*3=15で10桁を超えるので不適
Aが4桁の場合、4*3=12で10桁を超えるので不適

Aが3桁で、Bが1桁でCが1桁の場合、3+3+3=9
Aが3桁で、Bが1桁でCが2桁の場合、3+3+4=10
Aが3桁で、Bが1桁でCが3桁の場合、3+3+5=11
Aが3桁で、Bが2桁でCが2桁の場合、3+4+4=11
以上により、Aが3桁の場合も不適ですので、Aは2桁以下となります。

また、
A*BにA*Cを連結したものがパンデジタル数(9の倍数)なので
A*B + (10のA*Bの桁数乗)*A*C が9の倍数となります。
なので、(A*B+A*C)%9 == 0 を必要条件として使ってます。