Pythonで不幸な友達の数を数えるプログラム

n（偶数）の異なる友達の設定のリストがあるとします。各人iについて、preferences[i]は好みの順にソートされた友達のリストを保持します。したがって、リストの前の友人は、リストの後半の友人よりも優先されます。各リストの友達には、0からn-1までの整数で番号が付けられています。すべての友達は異なるペアに分けられます。ここで、pairs [i] =[xi、yi]は、xiがyiとペアになっている、および/またはyiがxiとペアになっていることを表します。しかし、xがyとペアになっていて、vとペアになっている友人uが存在する場合、友人xは不幸ですが、-

• xはyよりもuを優先し、
• uはvよりもxを優先します。

不幸な友達の数を見つけなければなりません。

したがって、入力が設定のようである場合=[[1、2、3]、[3、2、0]、[3、1、0]、[1、2、0]]ペア=[[0、1] 、[2、3]]の場合、最初の友人は人1が人0とペアになっているが、人0よりも人3を好み、人3は人2よりも人1を好むため、最初の友人は不幸であるため、出力は2になります。人3は人2とペアになっていますが、人2よりも人1を優先し、人1は人0よりも人3を優先するためです。

これを解決するには、次の手順に従います-

• グラフ：=グラフを作成するための隣接リスト、最初は空
• ペアの各ペア（s、e）について、
  • 設定の各設定について、
    • prefがendと同じ場合、
      • ループから抜け出す
    • グラフ[s、設定]：=1
  • 環境設定[e]の各設定について、
    • prefがstartと同じ場合、
      • ループから抜け出す
    • グラフ[e、設定]：=1
• 不幸：=0
• ペアの各ペア（s、e）について、
  • グラフの各設定について、
    • graph [pref] [s]が空でない場合、
      • 不幸：=不幸+1
      • ループから抜け出す
  • グラフ[end]の各設定について、
    を実行します。
    • graph [pref] [e]が空でない場合、
      • 不幸：=不幸+1
      • ループから抜け出す
• 不幸に戻る

例

理解を深めるために、次の実装を見てみましょう-

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