C++で配列の値から三角形を形成できるかどうかを判定する方法

この問題では、整数の配列が与えられ、その配列の要素を辺として使って非退化三角形を作成できるかどうかを判定します。

非退化三角形とは

非退化三角形とは、面積が正（0より大きい）となる三角形のことです。辺を a、b、c とする三角形が非退化であるための条件は以下の通りです。

a + b > c
a + c > b
b + c > a

問題例

具体的な例を見てみましょう。

• 入力：arr[2, 5, 9, 4, 3]
• 出力：Yes
• 説明：2、3、4 を辺とする三角形が形成できます。

解決アプローチ

この問題を解くには、配列の値が上記の条件を満たすかどうかを確認します。

素朴な解法としては、配列内のすべての三つ組（トリプレット）を直接チェックする方法が考えられます。しかし、これは計算量が O(N³) となり、配列が大きくなると非効率です。

より効率的な解法は、まず配列の要素をソートし、その後連続する3つの要素を順にチェックする方法です。ソート済みの配列では、隣接する2つの要素の和が次の要素以下であれば、それ以降の値をチェックする必要はありません（後続の値はさらに大きいため、条件を満たさないことが確定するからです）。この方法なら計算量は O(N log N) に抑えられます。

実装例

上記の解法を実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
bool isTrianglePossible(int arr[], int N){
    if (N < 3)
        return false;
    sort(arr, arr + N);
    for (int i = 0; i < N - 2; i++)
        if (arr[i] + arr[i + 1] > arr[i + 2])
            return true;
}
int main() {
    int arr[] = {5, 12, 13, 65, 6, 1};
    int N = sizeof(arr) / sizeof(int);
    cout<<"Creation of triangle from elements of array ";
    isTrianglePossible(arr, N)?cout<<"is Possible": cout<<"is not Possible";;
    return 0;
}

出力結果

Creation of triangle from elements of array is Possible

まとめ

配列の要素から三角形を形成できるかを判定する問題は、ソートを活用することで効率的に解くことができます。ポイントは、ソート後に「最小の2辺の和が最大の辺より大きいか」を連続する3要素で確認すれば十分だという点です。このテクニックは、他の幾何学的な判定問題にも応用できるので、ぜひ覚えておきましょう。