Pythonでグリッド内に作れる正方形の数を数えるプログラム

問題概要

等間隔に点が配置された、p行×q列のグリッドがあるとします。このグリッド上の点を頂点として作れる「一意な正方形」の総数を求めるのが本記事のテーマです。答えが非常に大きな値になる可能性があるため、結果は 10⁹ + 7 で割った余りとして返します。

ここでいう正方形とは、4つの点を頂点とし、4辺の長さがすべて等しい図形のことです。重要なのは、正方形は必ずしもグリッドの軸に平行である必要がないという点です。つまり、傾いた正方形も有効な解としてカウントします。

例えば、入力が p = 4、q = 4 の場合、出力は 20 になります。

解き方のアプローチ

この問題は、各正方形を「外接する正方形領域」のサイズごとに分類することで、効率的に数えることができます。手順は以下の通りです。

• i を 0 から min(r, c) − 1 までループする。
• 各 i について、ans += (r − i) × (c − i) × i を計算して加算する。
• 最後に ans を (10⁹ + 7) で割った余りを返す。

なぜこの式で求まるのか？

一辺が i マス分の正方形領域（(i+1) × (i+1) 個の点で構成される範囲）を考えると、その中には i 種類の異なる正方形が描けます。軸に平行な正方形から、最大限傾けた正方形までが含まれます。さらに、そのような領域はグリッド内に (r − i) × (c − i) 通りの位置に配置できます。したがって、各 i に対する正方形の数は (r − i) × (c − i) × i となり、これをすべての i について合計すれば答えが得られます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
    def solve(self, r, c):
        ans = 0
        for i in range(min(r, c)):
            ans += (r - i) * (c - i) * i
        return ans % (10 ** 9 + 7)

ob = Solution()
print(ob.solve(4, 4))

入力

p = 4
q = 4

出力

20

まとめ

このアルゴリズムの時間計算量は O(min(r, c)) であり、グリッドサイズが大きくなっても高速に動作します。傾いた正方形を含むすべての正方形を、外接領域のサイズごとに体系的に数え上げることで、単純な全探索よりもはるかに効率的に答えを導き出せるのがポイントです。