C++でN個の三角形の中から一意な三角形の数を求める方法

この問題では、サイズNの3つの配列 s1[]、s2[]、s3[] が与えられ、それぞれN個の三角形を表しています。与えられたN個の三角形の中から「一意な三角形」の数を見つけることが課題です。

三角形が一意であるためには、そのすべての辺が他のどの三角形とも一致しない必要があります。つまり、同じ辺の組み合わせを持つ三角形が他に存在してはいけません。

入力例

s1[] = {1, 5, 3}
s2[] = {2, 3, 2}
s3[] = {4, 2, 5}

出力例

1

説明

辺が 1、2、4 の三角形だけが一意です。残りの2つの三角形は、辺をソートするとどちらも {2, 3, 5} という同じ組み合わせになるため、一意とはみなされません。

解法アプローチ

この問題に対するシンプルな解決策は、一意な三角形の数を数えることです。

具体的には、まず各三角形の3つの辺をソートして正規化し、その辺の組み合わせをキーとしてマップ(std::map)に格納します。その後、マップ内で出現回数がちょうど1回の辺の組み合わせを数えれば、それが一意な三角形の数となります。

アルゴリズムの手順

1. 各三角形の3つの辺を1つのベクターに格納し、昇順にソートします。
2. ソート済みの辺の組み合わせをキーとして、マップに出現回数を記録します。
3. マップを走査し、出現回数が1の組み合わせの数をカウントして返します。

サンプルプログラム

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

int countUniqueTriangle(int a[], int b[], int c[], int n) {
    vector<int> triSides[n];
    map<vector<int>, int> m;
    for (int i = 0; i < n; i++) {
        triSides[i].push_back(a[i]);
        triSides[i].push_back(b[i]);
        triSides[i].push_back(c[i]);
        sort(triSides[i].begin(), triSides[i].end());
        m[triSides[i]]++;
    }
    int uniqueTriCount = 0;
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        if (itr->second == 1)
            uniqueTriCount++;
    }
    return uniqueTriCount;
}

int main() {
    int s1[] = { 1, 5, 3 };
    int s2[] = { 2, 3, 2 };
    int s3[] = { 4, 2, 5 };
    int N = sizeof(s1) / sizeof(s1[0]);
    cout << "一意な三角形の数は " << countUniqueTriangle(s1, s2, s3, N) << endl;
    return 0;
}

出力

一意な三角形の数は 1

計算量の分析

時間計算量: O(N log N) — 各三角形の辺のソートは要素数が3と一定のため O(1) で済み、マップへの挿入・走査に O(log N) かかるため、全体で O(N log N) となります。

空間計算量: O(N) — N個の三角形の辺の組み合わせをマップに格納するために必要です。