C++で直角三角形を形成できる斜辺と面積のペアの数を求める方法

この記事では、C++を使って、直角三角形を形成できる「斜辺」と「面積」の組み合わせが何通りあるかを求める方法を解説します。

問題の概要

与えられた斜辺 H と面積 A の組み合わせ (H, A) のうち、「H を斜辺、A を面積とする直角三角形」が実際に存在するものの総数を求めます。

ここで、各変数を次のように定義します。

• x：直角三角形の底辺
• y：直角三角形の高さ
• H：直角三角形の斜辺

数学的な導出

直角三角形の面積は次の式で表せます。

A = ( x × y ) / 2

両辺を変形すると、

4 × A² = ( x × y )²　…　(1)

また、三平方の定理（ピタゴラスの定理）より、

x² + y² = H²　…　(2)

(1) と (2) を連立して解くと、

4 × A² = x² ( H² − x² )

これを x² についての二次方程式とみなし、実数解が存在する条件として判別式 D ≥ 0 を適用すると、次の重要な条件が得られます。

H² ≥ 4 × A

つまり、これが「直角三角形が存在しうるための条件」です。

入力例と出力例

入力 : 配列 H[ ] = { 3, 6, 8 } : A[ ] = { 2, 31, 12 }
出力 : 4
説明 : 条件を満たす斜辺と面積のペア ( H, A ) は、( 3, 2 ), ( 6, 2 ), ( 8, 2 ), ( 8, 12 ) の4つです。

入力 : 配列 H[ ] = { 2, 5, 9 } : A[ ] = { 3, 11, 7 }
出力 : 4
説明 : 条件を満たすペアは、( 5, 3 ), ( 9, 3 ), ( 9, 11 ), ( 9, 7 ) の4つです。

解法のアプローチ

それでは、この問題を解くための2つの異なる手法を見ていきましょう。

1. 全探索（ブルートフォース）アプローチ

最もシンプルな方法です。考えられるすべての ( H, A ) のペアを生成し、それぞれが条件 H² ≥ 4 × A を満たすかどうかを判定して、条件を満たすペアの数をカウントします。

サンプルコード

#include <iostream>
using namespace std;
int main(){
    int H[ ] = { 2, 5, 9 }; // 斜辺の配列
    int s1 = sizeof(H)/sizeof(H[0]);
    int A[ ] = { 3, 11, 7 }; // 面積の配列
    int s2 = sizeof(A)/sizeof(A[0]);
    int count = 0; // カウントを0で初期化
    // すべてのペアを生成
    for (int i = 0; i < s1; i++) {
        for (int j = 0; j < s2; j++) {
            // 現在のペアが条件を満たすかどうかを判定
            if (H[i] * H[i] >= 4 * A[j]){
                count++;
            }
        }
    }
    cout << "Number of possible pairs of ( H, A ): " << count;
    return 0;
}

出力

Number of possible pairs of ( H, A ): 4

コードの解説

このコードでは、count 変数で条件を満たすペアの個数を記録し、二重ループによってすべての ( H, A ) のペアを生成しています。ただし、この方法の計算量は O(n²) であり、データ量が多い場合には非効率になります。そこで、次により効率的な手法を紹介します。

2. 効率的なアプローチ（二分探索）

この手法では、まず両方の配列を昇順にソートします。その上で、各斜辺の長さごとに条件 H² ≥ 4 × A を満たす最大の面積を二分探索で求めます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main (){
    int H[] = { 2, 5, 9 };
    int s1 = sizeof (H) / sizeof (H[0]);
    int A[] = { 3, 11, 7 };
    int s2 = sizeof (A) / sizeof (A[0]);
    int count = 0;
    // 両方の配列をソート
    sort (H, H + s1);
    sort (A, A + s2);
    int temp = -1;
    for (int i = 0; i < s1; i++){
        // 各斜辺の長さに対して二分探索を適用
        int flag1 = 0;
        int flag2 = s2 - 1;
        while (flag1 <= flag2){
            int mid = flag1 + (flag2 - flag1) / 2;
            if ((H[i] * H[i]) >= (4 * A[mid])){
                temp = mid;
                flag1 = mid + 1;
            }
            else{
                flag2 = mid - 1;
            }
        }
        if (temp != -1){ // 条件を満たす面積が見つかった場合
            count += temp + 1;
        }
    }
    cout << "Number of possible pairs of (H, A): " << count;
    return 0;
}

出力

Number of possible pairs of ( H, A ): 4

コードの解説

このコードでは、まず両方の配列を昇順にソートし、その後、二分探索を使って各斜辺の長さに対して条件を満たす最大の面積の位置を特定しています。

ここで重要なのは、面積の配列 A[ ] がソート済みであるため、たとえば最大の面積がインデックス3で見つかった場合、それより前のインデックスにある面積もすべて条件を満たすという点です。したがって、その時点で3つの有効なペアが一度に数えられるため、処理を大幅に高速化できます。

まとめ

この記事では、直角三角形を形成できる斜辺と面積のペアの数を求める問題を取り上げました。全探索アプローチ（計算量 O(n²）と、二分探索を活用した効率的なアプローチ（計算量 O(s1 log s2)）の2通りの実装方法を解説しました。データ规模が大きい場合は、二分探索版を選ぶことで実行時間を大きく短縮できます。本記事が皆さんの学習の一助となれば幸いです。