【Python】n×nボードから四隅の対角線セルを削除した後に残るセル数を求める方法

問題概要

一辺の長さ n を表す整数が与えられ、n × n のボードを考えます。4つの隅から伸びる2本の対角線上にあるセルをすべて削除し、その後に残っているセルの数を求めるのがこの問題です。

たとえば入力が n = 4 の場合、ボードは次のようになります(X が削除対象のセル、O が残るセルです)。

この場合、出力は 8 となります。

解法の考え方

この問題は、ボードを実際に生成しなくても次の式一つで答えを求められます。

• n × n − 2 × n + (n mod 2)

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

全体のセル数は n² です。2本の対角線にはそれぞれ n 個ずつセルがありますが、n が奇数の場合は中央のセルが両方の対角線に含まれて重複して数えられてしまいます。そこで「n mod 2」を加算することで、奇数の場合のみ重複分を補正しています。

• n が偶数の場合: 対角線上のセルは 2n 個(重複なし)→ 残りは n² − 2n 個
• n が奇数の場合: 対角線上のセルは 2n − 1 個(中央で重複)→ 残りは n² − 2n + 1 個

n = 4 の場合は 16 − 8 + 0 = 8 となり、期待どおりの出力が得られます。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
   def solve(self, n):
      return n*n - 2 * n + (n%2)

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

入力

4

出力

8

計算量について

この解法は数式だけで答えを導出するため、時間計算量は O(1) であり、追加のメモリも不要です。ボードをループで走査したり実際に構築したりする必要がないため、n が非常に大きい場合でも瞬時に結果を得られる点が大きなメリットです。