2021-03-12

『進化のからくり　現代のダーウィンたちの物語』を読み終わった

読了

三行感想

つまり今の琵琶湖にいるカワニナは移動前の琵琶湖とは違う、どこかから来たカワニナってこと？
ハードボイルドのアンガス！悟りを開いたミウラ！神スキルのヒラノ！(登場人物紹介)
インドに行ったミウラと帰ってきたミウラは別人っていう著述トリックかと思った

進化のからくり　現代のダーウィンたちの物語 (ブルーバックス)

作者:千葉聡
発売日: 2020/02/13
メディア: Kindle版

カラー図解進化の教科書第1巻進化の歴史 (ブルーバックス)

作者:カール・ジンマー,ダグラス.J・エムレン
発売日: 2016/11/16
メディア: 新書

進化の実～知らないうちに勝ち組人生～（コミック）： 3 (モンスターコミックス)

作者:そらの,美紅,U35
発売日: 2019/08/29
メディア: Kindle版

2021-01-23

Project Euler : Problem 52 『Permuted multiples』

算数 C# プログラミング

問題

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;
                }
            }
        }
    }
}