Pythonでボードを正方形に分割する最小コストを求めるアルゴリズム

問題の概要

縦 p、横 q のサイズを持つ1枚のボードがあるとします。このボードを p×q 個の正方形に切り分けるとき、切断にかかる総コストをできるだけ小さくしたいと考えます。それぞれの切断線には個別のコストが設定されており、その値があらかじめ与えられています。

例として、横方向の切断コストが X_slice = [3,2,4,2,5]、縦方向の切断コストが Y_slice = [5,2,3] の場合を考えてみましょう。

この場合、出力される最小コストは 65 となります。

解法のアプローチ（貪欲法）

この問題は貪欲法（Greedy Algorithm）を使って効率的に解くことができます。ポイントとなる考え方は次のとおりです。

• コストの高い切断線ほど早い段階で実行すると、その後の切断回数が増えても影響を受ける部分が少なくて済む。
• したがって、X方向・Y方向のすべてのコストを降順にソートし、大きい方から順に処理していく。
• ある時点での切断を実行するたびに、すでに存在する反対方向のピース数を掛けてコストに加算する。

アルゴリズムの手順

• res := 0（累積コスト）、horizontal := 1、vertical := 1、i := 0、j := 0 で初期化する。
• i < m かつ j < n の間、以下を繰り返す。
  • X_slice[i] > Y_slice[j] の場合：res += X_slice[i] × vertical とし、horizontal を +1、i を +1 する。
  • それ以外の場合：res += Y_slice[j] × horizontal とし、vertical を +1、j を +1 する。
• 残った X_slice の合計 total を求め、res += total × vertical を加算する。
• 残った Y_slice の合計 total を求め、res += total × horizontal を加算する。
• 最終的な res を返す。

Pythonでの実装例

それでは、上記のロジックを実際のPythonコードで確認してみましょう。

def minCost(X_slice, Y_slice, m, n):
    res = 0
    X_slice.sort(reverse=True)
    Y_slice.sort(reverse=True)
    horizontal = 1
    vertical = 1
    i = 0
    j = 0
    while i < m and j < n:
        if (X_slice[i] > Y_slice[j]):
            res += X_slice[i] * vertical
            horizontal += 1
            i += 1
        else:
            res += Y_slice[j] * horizontal
            vertical += 1
            j += 1
    total = 0
    while (i < m):
        total += X_slice[i]
        i += 1
    res += total * vertical
    total = 0
    while (j < n):
        total += Y_slice[j]
        j += 1
    res += total * horizontal
    return res

m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

入力

[3,2,4,2,5],[5,2,3]

出力

65

計算量について

このアルゴリズムでは、最初のソート処理が O(m log m + n log n)、その後のマージ処理が O(m + n) となるため、全体の時間計算量はソートの部分が支配的になります。貪欲法により、各切断のコストを「現在存在する交差するピース数」と掛け合わせていくことで、常に局所的に最適な選択を行い、結果として全体の最小コストを達成できます。