Pythonで解く：全ての友人同士が会話できるようにするための最小の教育人数を求めるアルゴリズム

ここでは、整数 n、配列 languages、配列 friendships が与えられているとします。n 個の言語には 1 から n までの番号が付いており、languages[i] は i 番目のユーザーが習得している言語の集合を表します。また、friendships[i] はペア [ui, vi] として、ユーザー ui と vi の間の友人関係を表します。

私たちの目的は、1つの言語を選んで一部のユーザーに教えることで、すべての友人同士が互いにコミュニケーションを取れるようにすることです。そのために教える必要のあるユーザーの最小人数を求めましょう。

なお、友人関係は推移的ではない点に注意が必要です。つまり、x が y の友人であり、y が z の友人であっても、x と z が友人であるとは限りません。

入出力の例

たとえば、次のような入力が与えられたとします。

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]

この場合、出力は 2 になります。ユーザー 1 とユーザー 3 に言語 3 を教えれば、すべての友人関係において会話が可能になるためです。教える対象は 2 人なので、答えは 2 となります。

解法のアプローチ

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

• lang: 各ユーザーが知っている言語の集合（set）を要素とするリストを作成します。
• not_comm: 会話できない友人関係に含まれるユーザーを格納する新しい集合（set）を用意します。
• friendships 内の各ペア (a, b) について以下を処理します。
  • a := a - 1、b := b - 1 としてインデックスを 0 始まりに調整します。
  • lang[a] と lang[b] に共通の言語がない場合（isdisjoint が真の場合）、a と b を not_comm に追加します。
• not_comm が空であれば、全員がすでに会話可能なので 0 を返します。
• cnt: 空のカウンタ（マップ）を用意し、not_comm に含まれる各ユーザー person について、lang[person] に含まれる各言語の出現回数を記録します。
• temp: cnt の値の中で最大のもの（＝not_comm 内で最も多く話されている言語の人数）を取得します。
• 最後に「not_comm のサイズ − temp」を返します。これは、最も多く話されている言語を全員に教えた場合に、新たに教育が必要な残りの人数に相当します。

Pythonでの実装例

それでは、上記の手順を実際のコードで確認してみましょう。

from collections import Counter

def solve(n, languages, friendships):
    lang = [set(L) for L in languages]

    not_comm = set()
    for a, b in friendships:
        a -= 1
        b -= 1
        if lang[a].isdisjoint(lang[b]):
            not_comm.add(a)
            not_comm.add(b)
    if not not_comm:
        return 0

    cnt = Counter()
    for person in not_comm:
        cnt.update(lang[person])
    temp = max(cnt.values())
    return len(not_comm) - temp

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]
print(solve(n, languages, friendships))

入力

3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]

出力

2

計算量とポイント

このアルゴリズムの計算量は、友人関係の数を F、各ユーザーの習得言語数を L とすると、おおむね O(F × L) となります。集合の isdisjoint メソッドを使うことで、2人のユーザーが共通の言語を持つかどうかを効率的に判定できるのがポイントです。

また、Counter を使って「会話できないグループ内で最も人気のある言語」を見つけ、その言語を一括して教える戦略を取ることで、教育すべき人数を最小化しています。これは貪欲法的な発想に基づいたシンプルかつ効果的な手法です。