【C++解説】水平・垂直カット後のケーキの最大面積を求めるアルゴリズム

問題概要

高さ h、幅 w の長方形のケーキがあるとします。さらに、整数型の配列 horizontalCuts と verticalCuts が与えられます。horizontalCuts[i] はケーキの上端から i 番目の水平カット位置までの距離を、verticalCuts[j] は左端から j 番目の垂直カット位置までの距離を表します。

これらの配列で指定されたすべての位置でカットを実行した後、切り分けられたピースの中で最大の面積を求めるのが目的です。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返してください。

入力例

たとえば、h = 5、w = 4、horizontalCuts = [1,2,4]、verticalCuts = [1,3] が入力された場合を考えてみましょう。

このとき出力は 4 になります。図において赤い線が水平・垂直のカット位置を示しており、カット後に最大面積となるのは緑色で示されたピースです。

解法アプローチ

この問題の鍵となる考え方はとてもシンプルです。最大のピースは、「隣接する水平カット間の間隔が最大の区間」と「隣接する垂直カット間の間隔が最大の区間」を掛け合わせた領域に必ず含まれるという点です。つまり、各方向の最大ギャップを見つけて掛け合わせるだけで答えが求まります。

具体的な手順は以下の通りです。

• 剰余演算用の関数 mul() を定義します。引数 a、b を受け取り、((a mod m) * (b mod m)) mod m を返します。
• メイン処理では h、w、配列 hh、配列 vv を受け取ります。
• hh と vv をそれぞれ昇順にソートします。
• hh の先頭に 0 を挿入し、末尾に h を追加します（ケーキの上下端を境界として扱うため）。
• 同様に vv の先頭に 0 を挿入し、末尾に w を追加します（左右端を境界として扱うため）。
• a := 0、b := 0 で初期化します。
• i = 1 から hh のサイズ未満までループし、a に隣接要素間の差分 hh[i] - hh[i-1] の最大値を記録します。
• 同じく vv についても、b に隣接要素間の差分の最大値を記録します。
• 最後に mul(a, b) を返します。

C++ 実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
    lli mul(lli a, lli b){
        return ((a % mod) * (b % mod)) % mod;
    }
    int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) {
        sort(hh.begin(), hh.end());
        sort(vv.begin(), vv.end());
        hh.insert(hh.begin(), 0);
        hh.push_back(h);
        vv.insert(vv.begin(), 0);
        vv.push_back(w);
        int a = 0;
        int b = 0;
        for (int i = 1; i < hh.size(); i++) {
            a = max(a, hh[i] - hh[i - 1]);
        }
        for (int i = 1; i < vv.size(); i++) {
            b = max(b, vv[i] - vv[i - 1]);
        }
        return mul(a, b);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,4}, v1 = {1,3};
    cout << (ob.maxArea(5,4,v,v1));
}

実行結果

入力：

5,4,{1,2,4}, {1,3}

出力：

4

計算量について

この解法では、カット位置のソートが支配的なコストとなります。水平方向 n 個、垂直方向 m 個のカットに対して、時間計算量は O(n log n + m log m)、追加の空間計算量は O(1)（ソートに必要な領域を除く）と非常に効率的です。境界値 0 と h・w を配列に加えることで、端から最初のカットまでの間隔も漏れなく考慮できる点がポイントです。