Problem85 長方形の数え上げ

問題

注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.



ぴったり2000000個の長方形を含むような長方形の格子は存在しない.
一番近い解を持つような格子の面積を求めよ.

ソース

using System;

class Program
{
    const long Shikii = 2000000;

    static void Main()
    {
        long AnswerDiff = int.MaxValue;
        long AnswerMenseki = int.MaxValue;

        for (int W = 1; W < int.MaxValue; W++) {
            long YokoSum = W * (W + 1) / 2;

            for (int H = W; H < int.MaxValue; H++) {
                long TateSum = H * (H + 1) / 2;

                long CurrCnt = YokoSum * TateSum;

                long CurrDiff = Math.Abs(CurrCnt - Shikii);
                if (CurrDiff < AnswerDiff) {
                    AnswerDiff = CurrDiff;
                    AnswerMenseki = W * H;

                    Console.WriteLine("{0}個の長方形を含む長方形(W={1},H={2},面積={3})を発見",
                        CurrCnt, W, H, AnswerMenseki);
                }
                if (Shikii < CurrCnt) break;
            }
            if (YokoSum * YokoSum > Shikii) break;
        }
    }
}

実行結果

省略
1997001個の長方形を含む長方形(W=1,H=1998,面積=1998)を発見
1999000個の長方形を含む長方形(W=1,H=1999,面積=1999)を発見
1999305個の長方形を含む長方形(W=2,H=1154,面積=2308)を発見
2000016個の長方形を含む長方形(W=3,H=816,面積=2448)を発見
1999998個の長方形を含む長方形(W=36,H=77,面積=2772)を発見

解説

4*3の長方形だと

内包する長方形の
横幅が4の場合、始点のXから終点のXまでの選び方は1通り
横幅が3の場合、始点のXから終点のXまでの選び方は2通り
横幅が2の場合、始点のXから終点のXまでの選び方は3通り
横幅が1の場合、始点のXから終点のXまでの選び方は4通り

内包する長方形の
縦幅が3の場合、始点のXから終点のXまでの選び方は1通り
縦幅が2の場合、始点のXから終点のXまでの選び方は2通り
縦幅が1の場合、始点のXから終点のXまでの選び方は3通り

以上のことをふまえて、
場合の数の積の法則と、等差数列の和の公式を使ってます。