C#でプロジェクトオイラーを解く（問題４３「部分文字列被整除性」）

Tweet

Pocket

どーも、みつおです。

問題

数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分文字列が面白い性質を持っている.

d1を上位1桁目, d2を上位2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

• d2d3d4=406 は 2 で割り切れる
• d3d4d5=063 は 3 で割り切れる
• d4d5d6=635 は 5 で割り切れる
• d5d6d7=357 は 7 で割り切れる
• d6d7d8=572 は 11 で割り切れる
• d7d8d9=728 は 13 で割り切れる
• d8d9d10=289 は 17 で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ.

出典：Problem43

解答

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problem43
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static long Solve()
        {
            long ret = 0;
            string strpandigi = "";

            //パンデジタル数を求める組合せ
            var perm = new Permutation();
            foreach (var n in perm.Enumerate(new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}))
            {
                //初期化
                strpandigi = "";
                
                //パンデジタル数を求める
                foreach (var x in n) strpandigi += x.ToString();

                //部分文字列が素数で割り切れるか
                if (IsSubStringPandigi(strpandigi)) ret += long.Parse(strpandigi);
            }

            return ret;
        }

        private static bool IsSubStringPandigi(string no)
        {
            bool ret = true;

            //部分文字列が面白い性質をもっているか判定
            if (ret == true) ret = int.Parse(no.Substring(1, 3)) % 2 == 0;
            if (ret == true) ret = int.Parse(no.Substring(2, 3)) % 3 == 0;
            if (ret == true) ret = int.Parse(no.Substring(3, 3)) % 5 == 0;
            if (ret == true) ret = int.Parse(no.Substring(4, 3)) % 7 == 0;
            if (ret == true) ret = int.Parse(no.Substring(5, 3)) % 11 == 0;
            if (ret == true) ret = int.Parse(no.Substring(6, 3)) % 13 == 0;
            if (ret == true) ret = int.Parse(no.Substring(7, 3)) % 17 == 0;

            return ret;
        }
    }

    public class Permutation
    {
        public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items)
        {
            if (items.Count() == 1)
            {
                yield return new T[] { items.First() };
                yield break;
            }
            foreach (var item in items)
            {
                var leftside = new T[] { item };
                var unused = items.Except(leftside);
                foreach (var rightside in Enumerate(unused))
                {
                    yield return leftside.Concat(rightside).ToArray();
                }
            }
        }
    }
}

出力

16695334890