Pongeponge

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2052

6倍した時桁上がりしない最上位桁

　6倍した時に1倍と同じ数字が使われているということは、最上位桁が桁上がりしない事と同じ意味。
仮に最上位桁が2だとすると、2×6=12で桁上がりするのでダメ。
2未満というと1しかないので、最上位桁は1

6倍した時に全体の桁が増えない最上位桁の次の桁

　1?…×6の時に最上位桁が桁上がりしないような?の最大値を知りたい。
仮に?が6だと16…×6=96…でいけるが、17×6は102…となってしまうことから?の最大値は6以下。

上限を求める

　16…x6=96…より、次の桁は6倍した時桁上がりしないように40未満になってほしい。
ということは6が最大値なので、値は166…になる。
見て分かるように以降6が続くので166…6が調べる上限。

下限を調べる

　探索の下限として1…を考える。
トップに1が含まれるということは、2～6倍するために桁のどこかに2～6が含まれないといけないはず。
つまり123456の6桁から探索を始めるべき…？(自信ない)

探索範囲の遷移は

　123456～166666→1123456～1666666という感じに変わっていく。

C#でのintの最大値

　int.MaxValueは2147483647で10桁あるからまぁ大丈夫でしょう多分。

同じ数字が使われているか確認する方法

　値を文字列化→char配列化→ソート→SequenceEqualで判定
もっといい方法があるかも。

コード

using System;
using System.Diagnostics;
using System.Linq;

namespace eu
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            Problem52();

            sw.Stop();
            Console.WriteLine($"Time {sw.ElapsedMilliseconds}");
        }

        private static void Problem52()
        {
            int startNum = 123456;
            int addNum = 100000;
            int maxNum = 166666;

            for (int i = startNum; i <= maxNum; i++)
            {
                var s1 = i.ToString().ToCharArray();
                var s2 = (i * 2).ToString().ToCharArray();
                var s3 = (i * 3).ToString().ToCharArray();
                var s4 = (i * 4).ToString().ToCharArray();
                var s5 = (i * 5).ToString().ToCharArray();
                var s6 = (i * 6).ToString().ToCharArray();

                Array.Sort(s1);
                Array.Sort(s2);
                Array.Sort(s3);
                Array.Sort(s4);
                Array.Sort(s5);
                Array.Sort(s6);

                if (s1.SequenceEqual(s2) & s3.SequenceEqual(s4) & s5.SequenceEqual(s6))
                {
                    if (s2.SequenceEqual(s3) & s4.SequenceEqual(s5))
                    {
                        Console.WriteLine($"{i}");
                        Console.WriteLine($"{i * 2}");
                        Console.WriteLine($"{i * 3}");
                        Console.WriteLine($"{i * 4}");
                        Console.WriteLine($"{i * 5}");
                        Console.WriteLine($"{i * 6}");

                        break;
                    }
                }

                if (i == maxNum)
                {
                    //初期値の更新
                    addNum = addNum * 10;
                    startNum = startNum + addNum - 1;

                    //最大値の更新
                    maxNum = maxNum * 10 + 6;
                }
            }
        }
    }
}