C++で長方形をちょうどk回カットしたときに得られる最小面積の最大値を求める方法

このチュートリアルでは、与えられた長方形に対してちょうどk回のカットを行ったとき、分割後のピースの中で最小となる面積が取りうる最大値を求めるプログラムをC++で解説します。

入力として長方形の2辺の長さ(n・m)とカット回数kが与えられます。目的は、指定された回数だけカットを行った結果として実現できる最小面積を計算し、その分割戦略を最適化することです。

アルゴリズムのポイント

長方形を片方の辺に沿って切ると、その辺は(k+1)個に分けられます。整数除算では端数が切り捨てられるため、どの方向に・どう配分してカットするかが最小ピースの面積を左右します。処理の流れは以下の通りです。

• k > (n + m - 2) の場合: 各方向には最大(n - 1)回・(m - 1)回しかカットできないため、これ以上のカットは不可能です。「Not possible」を出力します。
• k < max(m, n) - 1 の場合: すべてのカットを片方向に集中させるのが最適です。result = max(m × (n ÷ (k+1)), n × (m ÷ (k+1))) を計算します。
• 上記以外の場合: カットを両方向に分散させます。result = max(m ÷ (k - n + 2), n ÷ (k - m + 2)) を計算します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void max_area(int n, int m, int k) {
    if (k > (n + m - 2))
        cout << "Not possible" << endl;
    else {
        int result;
        if (k < max(m, n) - 1) {
            result = max(m * (n / (k + 1)), n * (m / (k + 1)));
        }
        else {
            result = max(m / (k - n + 2), n / (k - m + 2));
        }
        cout << result << endl;
    }
}
int main() {
    int n = 3, m = 4, k = 1;
    max_area(n, m, k);
    return 0;
}

出力結果

6

コードの解説

この例では、3×4の長方形に対して1回のカットを行います。max(m, n) - 1 = 3 であり、k = 1 はこれより小さいため、片方向へのカットを評価する分岐に入ります。

• 縦方向(辺の長さ3)に切る場合:4 × (3 ÷ 2) = 4 × 1 = 4
• 横方向(辺の長さ4)に切る場合:3 × (4 ÷ 2) = 3 × 2 = 6

2つの候補のうち大きい方である「6」が、最小ピース面積として確保できる最大値となります。つまり、長い辺を半分に割ることで、最も小さくなるピースでも面積6を保証できるというわけです。

まとめ

本記事では、長方形をちょうどk回カットしたときの最小ピース面積の最大値を求める方法を紹介しました。ポイントは、まずカット回数が実行可能な範囲内かを判定し、次に「片方向へ集中すべきか」「両方向へ分散すべきか」を場合分けすることです。整数除算の特性を踏まえたこの戦略により、効率的に最適解を導き出せます。