C++でコンテナ内の箱が占める最小面積を求める方法

正方形のコンテナで輸送したい n 組の箱があるとします。各組の箱の寸法はペア (a, b) として表され、それらは配列 dimensions に格納されています。箱を上下に積み重ねることはできず、各箱の幅を互いに平行にして並べる場合、箱がコンテナ内で占める面積を求める必要があります。ここでは、n 組すべてのペアについて、2つの箱を収めるために必要な最小の面積を計算します。

たとえば、入力が n = 4、dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}} の場合、出力は次のようになります。

64
25
36
16

解決の手順

この問題は、次の手順で解くことができます。

1. 結果を格納する変数 res を用意します。
2. n が 0 になるまで、以下の処理を繰り返します。
   • a に dimensions[n] の1番目の値、b に2番目の値を代入します。
   • res に「2 × min(a, b)」と「max(a, b)」のうち大きい方を代入します。
   • res × res の値を出力します。
   • n を1減らします。

ポイントは、2つの箱を並べるときに短い方の辺を揃えると、必要な正方形の一辺の長さが max(2 × min(a, b), max(a, b)) になるところです。あとはこの値を2乗すれば、コンテナ内で箱が占める最小面積が求まります。

res := 0
while n is non-zero, do:
    a := first value of dimensions[n]
    b := second value of dimensions[n]
    res := maximum of (2 * minimum of (a, b) and maximum of a and b)
    print(res * res)
    n := n - 1

C++実装例

それでは、実際のC++コードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(int n, vector<pair<int, int>> dimensions) {
    while (n--) {
        int a = dimensions[n].first;
        int b = dimensions[n].second;
        int res = max(2 * min(a, b), max(a, b));
        cout << res * res << endl;
    }
}

int main() {
    int n = 4;
    vector<pair<int, int>> dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}};
    solve(n, dimensions);
    return 0;
}

なお、この実装ではペアを配列の後ろから順に処理するため、出力は入力の順序と逆になります。各ペアごとに独立して面積を計算しているため、結果自体に影響はありません。

入力

4, {{2, 4}, {3, 6}, {2, 5}, {4, 6}}

出力

64
25
36
16