Project Euler : Problem 28 『Number spiral diagonals』

Spiral / mrhayata

問題

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

何ループ目か

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

表にするとこんな感じ。

ループ	0	1	2	…	(n - 1) / 2
サイズ	1	3	5	…	n

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

右下を見ていこう

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

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

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

1週分の和を求める

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

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

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

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

以上から、 m週目の l_m は
\( 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;
        }
    }
}