C#で Project Euler P8

はじめに

ソースの前に、簡単な方針を今回から書きます。

問題

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.
　
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
　
この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
　
EX 6桁の数123789から5個の連続する数字を取り出す場合, 12378と23789の二通りとなり, 後者の23789=3024が最大の総乗となる.
Problem 8 - PukiWiki

方針

構造を考慮して最適化する。
隣接した数字を乗じた数字は使いまわされる。
よって、各数字について右隣の数字と掛け合わせてこれを覚えておく。
上の手順で覚えた数字についても同じように右隣の数字と掛け合わせて覚えておく。
この手順を繰り返して作った数字列を層として考えると、
　1つの数字が掛け合わされた層(与えられた数字列の状態)
　2つの数字が掛け合された層
　4つの数字が掛け合された層
　8つの数字が掛け合された層
と、指数的に数字が掛け合わされ、木構像をとる。
その後、与えられた長さを2進数表記(2のべき乗の和に分解)し、ビットが立っている層のみを要素となった数字が重複しないようにずらして掛け合わせると、与えられた長さを乗じた値が得られる。
今回であれば長さは13であるため、
　$13_{(10)} = 1101_{(2)}$
となり、先頭の13文字で考えると
　$(7) × (3×1×6×7) × (1×7×6×5×3×1×3×3)$
と分割して考える。

解答

using System;
using System.Collections.Generic;

public static class P8
{
    public static void Main()
    {
        Console.WriteLine(Calc());
    }
    
    private const int MultiDepth = 13;
    private static Dictionary<Tuple<int, int>, long> multiMap = new Dictionary<Tuple<int, int>, long>();
    private static long Calc()
    {
        MakeMap(MultiDepth);
        int index = 0;
        long max = 0;
        while(multiMap.ContainsKey(Tuple.Create(MultiDepth, index)))
        {
            if(multiMap[Tuple.Create(MultiDepth, index)] > max)
            {
                max = multiMap[Tuple.Create(MultiDepth, index)];
            }
            index++;
        }
        return max;
    }
    
    
    private static void MakeMap(int depth)
    {
        var txt = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        
        for(var lIndex = 0; lIndex < txt.Length; lIndex++)
        {
            multiMap.Add(Tuple.Create(1, lIndex), (long)((byte)(txt[(int)lIndex]) & 0x0f));
        }
        for(int depthWork = depth >> 1, depthIndex = 2; depthWork > 0; depthWork >>= 1, depthIndex <<= 1)
        {
            var beforeDepth = depthIndex >> 1;
            for(int lIndex = 0; lIndex < txt.Length - depthIndex; lIndex++)
            {
                multiMap.Add(
                    Tuple.Create(depthIndex, lIndex),
                    multiMap[Tuple.Create(beforeDepth, lIndex)] *
                    multiMap[Tuple.Create(beforeDepth, lIndex + beforeDepth)]
                );
            }
        }
        
        if(!multiMap.ContainsKey(Tuple.Create(depth, 0)))
        {
            for(var lIndex = 0; lIndex < txt.Length - depth; lIndex++)
            {
                multiMap.Add(Tuple.Create(depth, lIndex), 1);
            }
            var offset = 0;
            for(int depthWork = depth, depthIndex = 1; depthWork > 0; depthWork >>= 1, depthIndex <<= 1)
            {
                if((depthWork & 1) == 1)
                {
                    for(int lIndex = 0; lIndex < txt.Length - depth; lIndex++)
                    {
                        multiMap[Tuple.Create(depth, lIndex)] *= multiMap[Tuple.Create(depthIndex, lIndex + offset)];
                    }
                    offset += depthIndex;
                }
            }
        }
    }
}

計算量
本プログラム：$O(n\log m)$
総当たり：$O(nm)$
n : 数字列の長さ
m : 乗じる数字の長さ