Q18 ショートケーキの日

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int LimitN = 40;
    static int[] HeihousuuArr;

    //平方数を列挙
    static void DeriveHeihousuuArr()
    {
        var HeihousuuList = new List<int>();
        for (int I = 0; I * I <= LimitN * 2; I++) {
            HeihousuuList.Add(I * I);
        }
        HeihousuuArr = HeihousuuList.ToArray();
    }

    static void Main()
    {
        DeriveHeihousuuArr();
        for (int LoopN = 2; LoopN <= LimitN; LoopN++) {
            Console.WriteLine("N={0}で解を調査します。", LoopN);
            if (HasAnswer(LoopN)) break;
        }
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal int[] NumArr;
    }

    //Nを引数として、解が存在するかを返す
    static bool HasAnswer(int pN)
    {
        int UB = pN - 1;
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrP = 1;
        WillPush.NumArr = new int[UB + 1];
        WillPush.NumArr[0] = 1; //1個目のイチゴは固定で1個とする
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.CurrP > UB) {
                Console.WriteLine("解を発見。");
                for (int I = 0; I <= UB; I++) {
                    Console.Write("{0,2},", Popped.NumArr[I]);
                    if (I % 10 == 9 || I == UB)
                        Console.WriteLine();
                }
                return true;
            }

            WillPush.CurrP = Popped.CurrP + 1;
            for (int I = 1; I <= pN; I++) {
                int wkInd = Array.IndexOf(Popped.NumArr, I, 0, Popped.CurrP);
                if (wkInd >= 0) continue;

                //Prevの要素との和が平方数であること
                int wkSum1 = I + Popped.NumArr[Popped.CurrP - 1];
                if (Array.BinarySearch(HeihousuuArr, wkSum1) < 0) continue;

                //Nextの要素との和が平方数であること
                if (Popped.CurrP == UB) {
                    int wkSum2 = I + Popped.NumArr[0];
                    if (Array.BinarySearch(HeihousuuArr, wkSum2) < 0) continue;
                }
                WillPush.NumArr = (int[])Popped.NumArr.Clone();
                WillPush.NumArr[Popped.CurrP] = I;
                stk.Push(WillPush);
            }
        }
        return false;
    }
}

実行結果

省略
N=30で解を調査します。
N=31で解を調査します。
N=32で解を調査します。
解を発見。
 1,15,10,26,23, 2,14,22,27, 9,
16,20,29, 7,18,31, 5,11,25,24,
12,13, 3, 6,30,19,17,32, 4,21,
28, 8,

解説

深さ優先探索でイチゴの数を順に求めてます。