Pythonで合計が1になる分数ペアの数をカウントするプログラム

分子と分母を [分子, 分母] の形式のリストで表した分数のリストが与えられます。各要素は「分子 ÷ 分母」という数値を表しています。ここでの課題は、足し合わせると合計が 1 になる分数のペアがいくつあるかを求めることです。

例えば、入力が fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]] の場合、出力は 4 になります。(2/7 + 5/7)、(3/12 + 3/4)、(3/4 + 1/4)、(4/14 + 5/7) の 4 つのペアが、いずれも合計 1 となるためです。

解き方のアルゴリズム

この問題は、各分数を最大公約数（GCD）で約分したうえで、辞書（マップ）を活用することで効率的に解けます。手順は以下のとおりです。

• 空の辞書 d と、答えを格納する変数 ans = 0 を用意します。
• fractions 内の各分数 i について、以下を繰り返します。
  • x := i[分子]、y := i[分母] として取り出します。
  • g := gcd(x, y)（x と y の最大公約数）を求めます。
  • x := x / g、y := y / g として分数を約分します。
  • temp_x := y − x、temp_y := y とします。これは「分数 x/y と足すと 1 になる分数（補数）」を表します。
  • もし (temp_x, temp_y) がすでに d に存在する場合は、ans := ans + d[(temp_x, temp_y)] とします。
  • d[(x, y)] := 1 + （d[(x, y)] が存在すればその値、存在しなければ 0）とします。
• 最後に ans を返します。

ポイント解説

なぜ GCD で約分するのかというと、「3/12」と「1/4」のように見た目が違っても値が同じ分数を、同じキーとして扱えるようにするためです。また、分数 x/y との和が 1 になる分数は必ず (y−x)/y となるので、辞書に「これまで登場した分数」を記録しておき、新しい分数の補数がすでに登録済みかどうかを確認すれば、ペアの総数を数えられます。分数の個数を n、分子・分母の最大値を M とすると、計算量は O(n log M) 程度に抑えられる点も大きなメリットです。

サンプルコード

import math

class Solution:
    def solve(self, fractions):
        d = {}
        ans = 0
        for i in fractions:
            x = i[0]
            y = i[1]
            g = math.gcd(x, y)
            x //= g
            y //= g
            temp_x = y - x
            temp_y = y
            if (temp_x, temp_y) in d:
                ans += d[(temp_x, temp_y)]
            d[(x, y)] = d.get((x, y), 0) + 1
        return ans

ob = Solution()
fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]
print(ob.solve(fractions))

なお、約分には整数除算の // を使います。通常の除算 / を使うと x や y が浮動小数点数になり、異なる分母を持つ同値の分数（例：3/12 と 1/4）が別のキーとして扱われてしまうためです。

入力

[[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]

出力

4