読者です 読者をやめる 読者になる 読者になる

Project Euler : Problem 28 『Number spiral diagonals』

プログラミング 算数 C#


SpiralSpiral / mrhayata

問題

projecteuler.net


 時計回りで渦巻き状に数字が並んでいる。
サイズが1001×1001の場合、対角線上の数字の総和はいくらか?


何ループ目か

 最初の1を0ループ目として、次の2から9を1ループ目とする。
0ループ目は1だけしかないのでサイズは1×1。
1ループ目は3×3、2ループ目は5×5。


表にするとこんな感じ。

ループ012(n - 1) / 2
サイズ135n


 サイズがn×nのとき、一番外側は(n - 1) / 2ループ目になる。
出題では1001×1001なので、
(1001 - 1) / 2 = 500
よって500ループ目まで調べる必要がある、ということになります。


右下を見ていこう

 対角線上にある数のうち、右下を数列 an とみなします。
\( a_{n} = 1, 3, 13, 31, \cdots \)
よくわからないまま差分を取ります。
\(b_{n} = 2, 10, 18, \cdots \)
何かに突き動かされるように、さらに差分を取ります。
\(c_{n} = 8, 8, \cdots \)


 cn が8,8,…ということは、bn は等差数列になっています。
\(b_{n} = 2 + 8n \)
anは各項の差がbn-1なので
\(a_{0} = 1 \\
a_{n} = a_{n-1}+b_{n-1} \ \ \ (n>0)\)


 これで右下の値を求めるめどがつきました。


1週分の和を求める

 中央の1は1周という感じじゃないですが、まぁ l0 とします。
\( l_{0} = 1 \)


 次は l1 の2~9、1周分を考えます。
右下の3を起点と考えると、
\( l_{1} = 3+5+7+9 \\
= 3+(3+2)+(3+4)+(3+6) \\
= 4 \times 3+12\)


 次に l2 の10~25を考えます。
右下の13を起点と考えると、
\( l_{1} = 13+17+21+25 \\
= 13+(13+4)+(13+8)+(13+12) \\
= 4 \times 13+24\)


 段々それっぽい規則性が見えてきましたが、確認のために l3 を。
\( l_{1} = 31+37+43+49 \\
= 31+(31+6)+(31+12)+(31+18) \\
= 4 \times 31+36\)


以上から、 m週目の lm
\( l_{0} = a_{0} = 1 \\
l_{m} = 4a_{m} + 12m \)
で求まることがわかりました。


 あとはプログラムに落とし込むだけ!


コード
using System;
using System.Diagnostics;

namespace Problem28
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(NumberSpiralDiagonals(1001));
        }

        static Int64 NumberSpiralDiagonals(int size)
        {
            int loops = (size - 1) / 2;

            int a = 0;
            Int64 sum = 0;
            for (int m = 0; m <= loops; m++)
            {
                a = ComputeA(a, m - 1);
                sum += LoopSum(a, m);
            }

            return sum;
        }

        /// <summary>
        /// m週目の右下の値aを求める
        /// </summary>
        static int ComputeA(int a, int m)
        {
            if (m < 0) return 1;

            int b = 2 + 8 * m;

            return a + b;
        }

        /// <summary>
        /// 一周分の和を求める
        /// </summary>
        static Int64 LoopSum(int a, int m)
        {
            if (m == 0) return a;

            return 4 * a + 12 * m;
        }
    }
}