Pythonで「不幸な友達」の数を数えるアルゴリズムと実装方法

問題の概要

n人(偶数)の友達がおり、それぞれの好みのリストが与えられます。各人 i に対して、preferences[i] は友達のリストを優先順位順に並べたもので、リストの先頭に近い友達ほど強く好まれます。友達には 0 から n-1 までの整数が振られています。

すべての友達は互いに重複しないペアに分けられています。pairs[i] = [xi, yi] は「xi と yi がペアである」ことを意味します。

ここで、友達 x が次の条件をすべて満たすとき、x を「不幸な友達」と呼びます。

• x は y とペアであり、u は v とペアである
• x は u を y より好んでいる
• u は x を v より好んでいる

この記事では、与えられたデータから不幸な友達の総数を求める方法を解説します。

入力例と出力例

たとえば、preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]、pairs = [[0, 1], [2, 3]] が入力された場合、出力は 2 になります。理由は以下の通りです。

• 友人 1 は友人 0 とペアですが、友人 3 を友人 0 より好んでおり、さらに友人 3 も友人 1 を自分のパートナーである友人 2 より好んでいるため、友人 1 は不幸です。
• 友人 3 は友人 2 とペアですが、友人 1 を友人 2 より好んでおり、さらに友人 1 も友人 3 を自分のパートナーである友人 0 より好んでいるため、友人 3 は不幸です。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. 隣接リスト形式のグラフ graph を用意します(初期状態は空)。
2. pairs の各ペア (s, e) について、次の処理を行います。
   • preferences[s] を先頭から走査し、パートナー e が現れた時点でループを抜けます。それ以外の友達 pref については、graph[s][pref] = 1 として記録します。これは「s が pref をパートナーより好んでいる」ことを意味します。
   • preferences[e] についても同様に処理します。
3. カウンター unhappy を 0 で初期化します。
4. 再び pairs の各ペア (s, e) について、次の処理を行います。
   • graph[s] 内の各 pref に対して、graph[pref] 側にも s が登録されているか(= 相互に好み合っているか)を確認します。存在すれば unhappy を 1 増やし、ループを抜けます。
   • e についても同様に確認します。
5. 最後に unhappy を返します。

ポイントは、各人の「パートナーより好ましい相手」だけをグラフに記録しておき、後から双方向の好み(相互に好み合う関係)が存在するかを調べる点です。これにより、不幸な友達を効率よく検出できます。

Pythonでの実装例

以下が実際の実装コードです。

from collections import defaultdict

def solve(preferences, pairs):
    graph = defaultdict(dict)
    for start, end in pairs:
        for pref in preferences[start]:
            if pref == end:
                break
            graph[start][pref] = 1
        for pref in preferences[end]:
            if pref == start:
                break
            graph[end][pref] = 1

    unhappy = 0

    for start, end in pairs:
        for pref in graph[start]:
            if graph[pref].get(start, None):
                unhappy += 1
                break
        for pref in graph[end]:
            if graph[pref].get(end, None):
                unhappy += 1
                break
    return unhappy

preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]
pairs = [[0, 1], [2, 3]]
print(solve(preferences, pairs))

入力

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]

出力

2

まとめ

このアルゴリズムでは、まず各人の「パートナーより好ましい友達」をグラフに記録し、その後「相互に好み合う関係」が存在するかどうかを調べることで、不幸な友達の数を数えています。計算量は O(n²) 程度に収まるため、n 人の好みのリストとペア情報から効率的に答えを導き出すことができます。