Project Euler 40

Problem 40

  • 10 から 99 までの整数をつなげたとき、その桁数は 桁数:2 * (100 - 10) です。
  • 100 から 999 までの整数をつながたとき、その桁数は 桁数:3 * (1000 - 100) です。
$ pry
[3] pry(main)> x = 10
=> 10
[4] pry(main)> x.to_s.length * (10*x - x)
=> 180
[5] pry(main)> (10..99).map(&:to_s).join.length
=> 180
[6] pry(main)> x = 100
=> 100
[7] pry(main)> x.to_s.length * (10*x - x)
=> 2700
[8] pry(main)> (100..999).map(&:to_s).join.length
=> 2700

10 から 99 まで、100 から 999 まで、と桁が同じものを全てつなげたときに何桁になるかを求めて、特定の桁の数字を求めます。

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

class PE040 {
    static int[] Digits(int n) {
        return n.ToString().Select(e => e - '0').ToArray();
    }

    static int Calc1(int n, int index, int x) {
        int ndigits = Digits(x).Length; // 桁数
        int inc = ndigits * (10*x - x); // ndigits 桁の数字を全て加えたときの合計文字数
        if (n > index + inc) {
            return Calc1(n, index + inc, 10*x);
        }
        else {
            int rest = n - index; // 残り文字数
            int q = rest / ndigits; // 数字を取り出す対象の整数
            int m = rest % ndigits; // 左端からのオフセット
            return Digits(x + q)[m];
        }
    }
    static int Calc(int n) {
        // 0.[1]23456789101112131415....
        //    ^
        //    |
        //    index=1 右隣りが index=2
        //    x=1 (1からの整数)
        
        int index = 1; // 現在のインデックスの位置
        int x = 1;     // スタートする数値
        return Calc1(n, index, x);
    }
    
    static void Main() {
        int[] xs = { 1, 10, 100, 1000, 10000, 100000, 1000000 };
        int ans = xs.Aggregate(1, (a, b) => a * Calc(b));
        Console.WriteLine(ans);
    }
}