C++で長方形を作成する – 目標面積から最適な縦横比を求める方法

特定の面積を持つ矩形のウェブページ領域が与えられたとします。私たちの課題は、次の要件をすべて満たすように、長さ L と幅 W を持つ矩形のウェブページを設計することです。

• ウェブページの面積（L × W）は、指定された目標面積と一致しなければなりません。
• 幅 W は長さ L を超えてはならず、L >= W を満たす必要があります。
• L と W の差は、できるだけ小さくなるようにします。

例えば、入力が 4 の場合、出力は [2, 2] になります。目標面積が 4 であるとき、考えられる組み合わせは [1, 4]、[2, 2]、[4, 1] の3通りです。しかし、要件2により W ≤ L でなければならないため [1, 4] は不正解となり、要件3により差を最小化する観点から [4, 1] よりも [2, 2] が適切です。したがって、答えは長さ L = 2、幅 W = 2 となります。

解法のアプローチ

この問題を解くために、次の手順に従います。

• i を「area の平方根」として初期化し、i > 0 の間、i を 1 ずつ減らしながらループを実行します。
  • もし area % i == 0（area が i で割り切れる）であれば：
    • 配列 v を定義し、{area / i, i} を挿入します。
    • v を返して終了します。
• ループが完了しても割り切れる値が見つからない場合は、{-1, -1} を返します。

このアプローチが有効な理由は、平方根から探索を始めることで、最初に見つかった約数のペアが L と W の差が最小となる組み合わせになるためです。計算量も O(√n) に抑えられ、非常に効率的です。

実装例

それでは、実際のコードを見ながら理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> constructRectangle(int area) {
        for (int i = sqrt(area); i > 0; i--) {
            if (area % i == 0) {
                vector<int> v{ area / i, i };
                return v;
            }
        }
        return { -1, -1 };
    }
};
main(){
    Solution ob;
    print_vector(ob.constructRectangle(4));
}

入力

4

出力

[2, 2]

コードのポイント

• 平方根からの探索： √area から降順に整数を調べることで、最初に見つかる約数のペアが必ず「幅と長さの差が最小」の組み合わせになります。
• 剰余演算による判定： area % i == 0 を使うことで、i が area の約数かどうかを簡単に判定できます。
• 返り値の順序： 結果は {area / i, i} の順で返されるため、常に長さ L が幅 W 以上になることが保証されます。