Pythonでn×mの長方形内に配置できる2×1サイズの長方形の個数を求める方法

問題概要

2つの整数 n と m が与えられたとき、サイズ n × m の長方形の内部に、サイズ 2 × 1 の小さな長方形を最大いくつ配置できるかを求めます。

ただし、以下の条件を満たす必要があります。

• どの2つの小さな長方形も互いに重なってはならない。

• すべての小さな長方形は、大きな長方形の内部に完全に収まっていなければならない。ただし、外側の長方形の辺に接することは許容される。

入力例

たとえば、n = 3、m = 3 の場合、出力は 4 になります。

3×3のマス目には、2×1の長方形（ドミノ）を4つ配置でき、残りの1マスだけが空きとなります。

解き方のアプローチ

この問題は、面積の考え方と偶奇の判定を使うことで、シンプルな計算式で解くことができます。手順は以下の通りです。

• n が偶数の場合： n を2で割った数だけ縦方向に並べられるので、(n / 2) * m を返します。

• m が偶数の場合： 同様に、(m // 2) * n を返します。

• n も m も奇数の場合： 面積 n × m は奇数になるため、必ず1マス余ります。したがって、(n * m - 1) // 2 を返します。

ポイントは、2×1の長方形は常に2マス分の面積を占めるため、答えは「使えるマスの総数 ÷ 2」で求められるということです。両方の辺が奇数のときだけ、1マスがどうしても埋められずに残ります。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def count_rect(n, m):
    if (n % 2 == 0):
        return (n / 2) * m
    elif (m % 2 == 0):
        return (m // 2) * n
    return (n * m - 1) // 2

n = 3
m = 3
print(count_rect(n, m))

入力:

3, 3

出力:

4

まとめ

n×mの長方形に2×1の長方形を何個配置できるかという問題は、偶奇の判定だけでO(1)の計算量で解けることがわかりました。片方でも偶数なら全マスを埋め尽くせますが、両方とも奇数の場合は必ず1マス余る、という性質を覚えておくと、類似のタイル敷き詰め問題にも応用できます。