なるほど、再帰DFSか…(今回私は解説ACです)
問題概要
N人をT個のチームに分けたい。しかし、その中には仲の悪いペアがM組存在し、人A[i]とB[i]は同じグループに入れてはいけない。チーム分けの方法は何通りか。
主な制約
- 1 ≦ T ≦ N ≦ 10
- 0 ≦ M ≦ N(N-1)/2
解説
N ≦ 10より、今回は少なくとも10人しかいないので、実際に全てのグループの分け方を列挙することができる。最大の数に関しては、最後にある「おまけ: 今回の条件における最大の通り数」参照。
列挙するためには再帰関数を用いる。状況を示すリストと、最後に入れた人eを引数として持つ再帰関数を作り、「各グループに人e+1を入れられるなら入れて再帰、新しいグループを作れるなら作って再帰し、最終的にTグループになっていればカウント」という動作をするように実装する。詳しくは実装を見てほしい。
実装(Python)
# Pythonで再帰関数を使うためのおまじない import sys sys.setrecursionlimit(10**8) N, T, M = map(int, input().split()) L = [list(map(int, input().split())) for _ in range(M)] # 仲の悪い相手を管理するリスト incompatible_list = [set() for _ in range(N+1)] # 隣接リストのように入れていく for a,b in L: incompatible_list[a].add(b) incompatible_list[b].add(a) # 答えをカウントする変数 cnt = 0 # group_list: 現時点でのグループの状況, e: 最後に入れた要素 def rec(group_list, e): # 関数内でもcntを使えるようにグローバル化 global cnt # もし最後の人まで分け終わっていたら if e == N: # もしグループがT個でなく、条件に合っていないなら if len(group_list) != T: # 何もせず終了 return # 条件に合っているので、カウントして終了 cnt += 1 return # 人eまで入れたので、次は人e+1を入れたい # 次に入れる人e+1を、グループiに入れられるかを示すリスト can_add = [True] * len(group_list) # i: e+1と仲の悪い相手 for i in incompatible_list[e+1]: # j: 各グループの番号 for j in range(len(group_list)): # もしe+1と仲の悪い相手iがグループjにいるなら if i in group_list[j]: # グループjには入れられない can_add[j] = False # 各グループにおいて for i in range(len(group_list)): # もしe+1をグループiに追加できるなら if can_add[i]: # 追加 group_list[i].add(e+1) # 再帰関数 rec(group_list, e+1) # 関数が終わったら元に戻しておく group_list[i].discard(e+1) # もし新しいグループを作る余裕があるなら if len(group_list) < T: # グループを追加 x = group_list + [{e+1}] rec(x,e+1) # 最初は空のリスト、1(0+1)を次に追加するので0 rec([], 0) # 答えを出力 print(cnt)
おまけ: 今回の条件における最大の通り数
仲の悪いペアがいないとき、N人をTペアに分ける通り数は「第二種スターリング数」というもので表すことができるようだ。これに基づいて計算すると、1 ≦ T ≦ N ≦ 10の条件の中で第二種スターリング数が最大になる「N = 10, T = 5」の時でも42525通りしかない。従って、十分に列挙可能であるといえる。
第二種スターリング数は以下の再帰関数で計算可能(ただしn ≧ k, n < kなら0)。試しに入力例3のN=6, K=4を入れてみると確かに出力例と同じ「65」が返ってくる。
# 第二種スターリング数 def S(n, k): if k == 1 or n == k: return 1 return S(n - 1, k - 1) + k * S(n - 1, k)
参考文献
- http://www.igaris.com/math/c.pdf 「2 ボールが区別でき, 箱が区別できない場合」より
- https://manabitimes.jp/math/841
