Problem173 いくつの穴あき正方形laminaを作れるか?

問題

輪郭が正方形で, 正方形の穴を持ち, 縦にも横にも対称性をもつようなものをlaminaeと定義する.
例えば, 32個のタイルを使うと以下の二つの異なったlaminaが作れる.



100個以下のタイルを使うと, 41種類のlaminaが作れる.
100万個以下のタイルを使うと何種類のlaminaが作れるか?

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Solve(100);
        Solve(1000000);
    }

    static void Solve(int pJyougen)
    {
        Console.WriteLine("{0}個以下のタイルでの解を検証します", pJyougen);

        long CntOdd = DeriveLaminaCnt(pJyougen, false);
        long CntEven = DeriveLaminaCnt(pJyougen, true);

        Console.WriteLine("奇数幅の正方形だと、{0}通り", CntOdd);
        Console.WriteLine("偶数幅の正方形だと、{0}通り", CntEven);
        Console.WriteLine("解は{0}通り", CntOdd + CntEven);
        Console.WriteLine();
    }

    static long DeriveLaminaCnt(int pJyougen, bool pIsEven)
    {
        var MensekiList = new List<long>();

        long Hen = (pIsEven == false ? 1 : 2);
        while (true) {
            long Gaisyuu = Hen * 2 + (Hen - 2) * 2;
            if (Gaisyuu > pJyougen) break;

            MensekiList.Add(Hen * Hen);
            Hen += 2;
        }
        long[] MensekiArr = MensekiList.ToArray();
        int UB = MensekiArr.GetUpperBound(0);

        long WillReturn = 0;
        for (int I = 0; I <= UB; I++) {
            int MinInd = ExecNibunHou(MensekiArr, MensekiArr[I] - pJyougen, I);
            WillReturn += I - MinInd;
        }
        return WillReturn;
    }

    //2分法で、MinVal以上の、最小の添字を返す
    static int ExecNibunHou(long[] pMensekiArr, long pMinVal, int pR)
    {
        if (pMensekiArr[0] >= pMinVal) return 0;
        int L = 0;
        int R = pR;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            //Console.WriteLine(
            //    "L={0},Mid={1},R={2}。pMensekiArr[{0}]={3}。pMensekiArr[{1}]={4}。pMensekiArr[{2}]={5}",
            //    L, Mid, R, pMensekiArr[L], pMensekiArr[Mid], pMensekiArr[R]);

            bool IsOK = (pMensekiArr[Mid] >= pMinVal);
            if (IsOK) R = Mid;
            else L = Mid;
        }
        return R;
    }
}

実行結果

100個以下のタイルでの解を検証します
奇数幅の正方形だと、21通り
偶数幅の正方形だと、20通り
解は41通り

1000000個以下のタイルでの解を検証します
奇数幅の正方形だと、786473通り
偶数幅の正方形だと、786256通り
解は1572729通り

解説

外周のマス目の数の累積和を求めておいて、2分法と組み合わせてます。