C++でユニークな分数リストを作成する方法：約分・重複削除・昇順ソート

問題概要

[分子, 分母]（分子 / 分母）というペアからなる分数のリストが与えられます。このリストをもとに、次の条件をすべて満たす新しい分数リストを作成するのが課題です。

• 既約形にする：各分数をこれ以上約分できない形まで簡略化します。（例：20/14 → 10/7）
• 重複を削除する：約分した結果が同一になる分数は1つだけ残します。
• 昇順にソートする：分数の実際の値に基づいて小さい順に並べます。
• 符号の扱い：負の分数の場合、「-」の記号は必ず分子側に付けます。

たとえば、入力が {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}} の場合、出力は [[-1, 2], [2, 1], [7, 3], [5, 1]] となります。

解法の考え方

この問題は「約分 → ソート → 重複除去」という3つのステップに分けて考えるとシンプルになります。具体的な手順は以下の通りです。

1. n := 配列 v のサイズとします。
2. 一時的な結果を格納する配列 r を用意します。
3. i := 0 から n-1 までループします。
   • c := |v[i][0]| と |v[i][1]| の最大公約数（GCD）を求めます。
   • v[i][0] := v[i][0] / c、v[i][1] := v[i][1] / c として約分します。
   • {v[i][0], v[i][1]} を配列 r の末尾に追加します。
4. 配列 r を、分数の実際の値を基準に昇順ソートします。
5. 最終結果を格納する配列 ret を用意します。
6. 配列 r の各要素を調べ、ret が空であるか、ret の末尾の要素と値が異なる場合にのみ追加します。ソート後のリストでは重複が必ず隣り合うため、直前の要素との比較だけで重複を排除できます。
7. ret を返します。

C++実装例

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

void print_vector(vector<vector<auto>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        double aa = (double)a[0] / (double)a[1];
        double bb = (double)b[0] / (double)b[1];
        return aa < bb;
    }

    vector<vector<int>> solve(vector<vector<int>>& v) {
        int n = v.size();
        vector<vector<int>> r;
        for (int i = 0; i < n; i++) {
            int c = __gcd(abs(v[i][0]), abs(v[i][1]));
            v[i][0] /= c;
            v[i][1] /= c;
            r.push_back({v[i][0], v[i][1]});
        }
        sort(r.begin(), r.end(), cmp);
        vector<vector<int>> ret;
        for (int i = 0; i < r.size(); i++) {
            if (ret.empty() || ret.back() != r[i]) {
                ret.push_back(r[i]);
            }
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}};
    Solution ob;
    print_vector(ob.solve(v));
}

入力

{{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}

出力

[[-1, 2],[2, 1],[7, 3],[5, 1]]

実装のポイント

• __gcd() はGCCが提供する最大公約数を求める関数です。C++17以降では、標準ライブラリの std::gcd() を利用することもできます。
• GCDの計算前に abs() で絶対値を取得するため、分数の符号は分子側にそのまま保持されます。
• カスタム比較関数 cmp では、分子・分母を double 型にキャストして割り算を行い、実際の値で大小を判定しています。
• ソート済みのリストでは同じ値の要素が必ず隣接するため、全要素の組み合わせを比較せずとも、直前の要素との比較だけでO(n)の計算量で重複を削除できます。