Project Euler : Problem 24 『Lexicographic permutations』

列 / aun333

問題

projecteuler.net

　0,1,2,3,4,5,6,7,8,9を重複の無いように組み合わせる。
作れる全ての数字を辞書順に並び替えたとき、100万番目に来る数字は何か？

力技でやるなら

　全パターンを配列に突っ込んで並び替えて100万番目を出力すればいい。
でも確実に100万以上あるのが分かってるしなぁ。

　とりあえず全パターンがいくらあるのか計算してみる。
文字は0から9の10通りだから、
10! = 10×9×8×7×6×5×4×3×2×1 = 3628800
だいたい363万通り。
多すぎるので力技は却下の方向で。

全体から見てどの位置にいるのかを考える

　使える文字がN = n₀, n₁, … , n_m-1, n_mの場合で考える。
まず全パターン数Pを求める。
(m+1)×m×…×2×1 = (m+1)!

　辞書順ランクr+1番目の値を求める場合、(m+1)!を今取れる文字数m+1で割る。
(m+1)!/(m+1) = m!
次に求めたいランク-1の値をm!で割る。
r/m! = p₀ … q₀
m_p0を得て、Nからm_p0を消す。

　次はm!を今取れる文字数mで割る。
m!/m = (m-1)!
前回の余りのq₀を(m-1)!で割る。
q₀/(m-1)! = p₁ … q₁
そしてm_p1を得て、Nからm_p1を消す。
あとはm=1になるまでくりかえすだけ。

　qを出現順にp₀p₁…p_mと並べると、求めたいランクの文字になっている。

コード

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Problem24
{
    class Program
    {
        static List<int> digits = new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        static void Main(string[] args)
        {
            Int64 allPatternNum = Factorial(digits.Count);


            Debug.WriteLine(RankingNumber(allPatternNum, 1000000));

        }

        /// <summary>
        /// n!を求める
        /// </summary>
        static Int64 Factorial(int n)
        {
            if (n == 0) return 0;

            Int64 p = 1;

            for (int i = 2; i <= n; i++)
            {
                p *= i;
            }

            return p;
        }

        /// <summary>
        /// n番目の番号を求める
        /// </summary>
        /// <param name="apn">全パターン数</param>
        /// <param name="rank">求める値が何番目か</param>
        static String RankingNumber(Int64 apn, Int64 rank)
        {
            //ランクは1番から始まる＆最大数以上はなし
            if (rank <= 0) return "うわっ…私のRank、低すぎ…？";
            if (rank > apn) return "常識的に考えてRank高すぎ";
            rank--;

            List<int> d = new List<int>(digits);
            String s = string.Empty;


            for (int i = d.Count; i >= 1; i--)
            {
                apn = apn / i;
                int p = (int)(rank / apn);
                rank = rank % apn;
                s += d[p].ToString();
                d.RemoveAt(p);
            }

            return s;
        }
    }
}

答え

　2783915460

場合の数 2―作業性の特訓 書き上げて解く組み合わせ (思考力算数練習張シリーズ 24)

組合せ論入門

「なぜ? どうして?」をとことん考える高校数学 (BERET SCIENCE)

Project Euler : Problem 23 『Non-abundant sums』

Abundant Beauty / Jitabebe

問題

projecteuler.net
　2つの過剰数の和で表現できない正の整数の総和はいくらか？
既知の事柄として、28123より大きい数は2つの過剰数の和で表現できる。

過剰数(Abundant number)？

　過剰数とは、ある数nの自身を含まない約数全てを足した結果がnを超える数、らしい。
例えば、12の約数d(12)は1,2,3,4,6,12。
このうち、自分自身以外の和を取ると、
1+2+3+4+6 = 16
となって12を超えちゃう。だから12は過剰数。

こういうのはどうだろう

約数の和リストを28123まで作成する
↓
過剰数だけピックアップする
↓
28123以下になる過剰数の和リストを作成する
↓
過剰数の和リストの数以外を全て足す
↓
身体は闘争を求める
↓
アーマードコアの新作が出る

コード

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

namespace Problem23
{
    class Program
    {
        //上限
        static int MaxNum = 28123;

        static void Main(string[] args)
        {
            int[] an = CreateAbundantNumbersArray(CreateSumDivisorsArray());

            Debug.WriteLine(Result(an));
        }

        /// <summary>
        /// 約数の和リストを作成
        /// </summary>
        static Int64[] CreateSumDivisorsArray()
        {
            Int64[] SumDivisors = new Int64[MaxNum + 1];

            for (int p = 2; p <= MaxNum / 2; p++)
            {
                for (int i = p * 2; i < SumDivisors.Length; i += p)
                {
                    SumDivisors[i] += p;
                }
            }

            for (int i = 2; i < SumDivisors.Length; i++)
            {
                SumDivisors[i] += 1;

                if (SumDivisors[i] > MaxNum) SumDivisors[i] = 0;
            }

            return SumDivisors;
        }

        /// <summary>
        /// 過剰数の和リストを作成
        /// </summary>
        /// <param name="sd">約数の和リスト</param>
        static int[] CreateAbundantNumbersArray(Int64[] sd)
        {
            List<int> an = new List<int>();
            List<int> an2 = new List<int>();

            //過剰数リスト
            for (int i = 0; i < sd.Length; i++)
            {
                if (sd[i] > i)
                {
                    an.Add(i);
                }
            }

            //過剰数の和リスト
            for (int i = 0; i < an.Count - 1; i++)
            {
                for (int j = i; j < an.Count; j++)
                {
                    int tmp = an[i] + an[j];
                    if (tmp <= MaxNum)
                    {
                        an2.Add(tmp);
                    }
                    else
                    {
                        break;
                    }
                }
            }

            //ソートと重複の削除
            an2.Sort();

            return an2.Distinct().ToArray();
        }

        /// <summary>
        /// 過剰数の和で表せられない数を全部足す
        /// </summary>
        /// <param name="an2">過剰数の和リスト</param>
        static Int64 Result(int[] an2)
        {
            Int64 sum = 0;
            int count = 0;

            for (int i = 0; i <= MaxNum; i++)
            {
                if (an2[count] == i)
                {
                    count++;
                }
                else
                {
                    sum += i;
                }
            }

            return sum;
        }
    }
}

答え

　4179871

老いる家 崩れる街 住宅過剰社会の末路 (講談社現代新書)

過剰な資本の末路と、大転換の未来　なぜ歴史は「矛盾」を重ねるのか

「過剰反応」社会の悪夢 (角川新書)

Project Euler : Problem 22 『Names scores』

names / okfn

問題

projecteuler.net
　names.txt内の名前を辞書順にランク付けする。
その後、名前の各文字がアルファベット何文字目かを調べて和をとり、名前のランクと掛ける。
names.txt内の総ネームスコアはいくらか？

つまり？

　ABCさんとHIさんとDEFGさんがいるとする。
辞書順に並ぶとこう。

ABC, DEFG, HI

　ランクはABCさんが1、DEFGさんが2、HIさんが3。
次に各アルファベットが何文字目か調べて和をとる。
Aは1番目だから…

ABC, DEFG, HI
→　1+2+3, 4+5+6+7, 8+9
→　6, 22, 17

これにランクを掛けて、和をとる。

6×1 + 22×2 + 17×3
= 6 + 44 + 34
= 84

　そんなに難しくなさそう。

コード

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

namespace Problem22
{
    class Program
    {
        static String[] names;

        static void Main(string[] args)
        {
            ReadNames();

            Debug.WriteLine(TotalNameScore());
        }

        /// <summary>
        /// 名前ファイルの読み込みとソート
        /// </summary>
        static void ReadNames()
        {
            String path = @"..\..\names.txt";

            names = File.ReadAllText(path).Split(',').Select(obj => obj.Replace("\"", "")).ToArray();

            Array.Sort(names);
        }

        /// <summary>
        /// 全名前スコアを求める
        /// </summary>
        static Int64 TotalNameScore()
        {
            Int64 sum = 0;

            for (int i = 0; i < names.Length; i++)
            {
                int rank = i + 1;
                int score = 0;

                foreach (char c in names[i])
                {
                    score += (c - '@');
                }

                sum += (rank * score);
            }

            return sum;
        }
    }
}

答え

　871198282

幻想人名辞典

世界史のための人名辞典

クリエーターのためのネーミング辞典 (一般向辞典)

『新約 とある魔術の禁書目録(17)』を読み終わった

　ウィッチクラフトワークスと同じく買うの忘れてた。

三行感想

・イン何とかさんは放置に次ぐ放置で不憫だ
・上里が帰ってくる前後に凄く消化不良感がある
・アレイ星さん何してんの…

新約 とある魔術の禁書目録(17) (電撃文庫)

新約 とある魔術の禁書目録 (16) (電撃文庫)

とある魔術の禁書目録(17) (ガンガンコミックス)