課題 · アルゴリズム 上級 Python ·

Maximum bipartite matching

def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:

max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])  # -> 3
max_matching(2, 1, [[0, 0], [1, 0]])  # -> 1

• #1Anthropic Claude Sonnet 5.5正解 · 11 / 11 件のテストにパス回答時間 9.7 秒 · 実行時間 453 ms · $0.02

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	1 ms

  ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 ms
  コード

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          if 0 <= u < n_left and 0 <= v < n_right:
              adj[u].append(v)
      matchL = [-1] * n_left
      matchR = [-1] * n_right
      res = 0
      for u in range(n_left):
          for v in adj[u]:
              if matchR[v] == -1:
                  matchR[v] = u
                  matchL[u] = v
                  res += 1
                  break
      while True:
          dist = [-1] * n_left
          q = []
          for u in range(n_left):
              if matchL[u] == -1 and adj[u]:
                  dist[u] = 0
                  q.append(u)
          found = False
          qi = 0
          while qi < len(q):
              u = q[qi]
              qi += 1
              du = dist[u] + 1
              for v in adj[u]:
                  w = matchR[v]
                  if w == -1:
                      found = True
                  elif dist[w] == -1:
                      dist[w] = du
                      q.append(w)
          if not found:
              break
          it = [0] * n_left
          aug = 0
          for r in range(n_left):
              if matchL[r] != -1 or dist[r] != 0:
                  continue
              stack = [r]
              while stack:
                  u = stack[-1]
                  au = adj[u]
                  i = it[u]
                  pushed = False
                  done = False
                  while i < len(au):
                      v = au[i]
                      i += 1
                      w = matchR[v]
                      if w == -1:
                          it[u] = i
                          done = True
                          break
                      if dist[w] == dist[u] + 1:
                          it[u] = i
                          stack.append(w)
                          pushed = True
                          break
                  if done:
                      for x in stack:
                          v = adj[x][it[x] - 1]
                          matchL[x] = v
                          matchR[v] = x
                      aug += 1
                      break
                  if pushed:
                      continue
                  it[u] = i
                  dist[u] = -2
                  stack.pop()
          if aug == 0:
              break
          res += aug
      return res

• #2MiniMax M3.1 Flash正解 · 11 / 11 件のテストにパス回答時間 5.9 秒 · 実行時間 691 ms · $0.0016

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	<1 ms

  ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 ms
  コード

  from collections import deque
  
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0:
          return 0
  
      adj = [None] * n_left
      for u in range(n_left):
          adj[u] = []
      seen_sets = [set() for _ in range(n_left)]
      for e in edges:
          u = e[0]
          v = e[1]
          s = seen_sets[u]
          if v not in s:
              s.add(v)
              adj[u].append(v)
      for u in range(n_left):
          adj[u] = list(seen_sets[u])
  
      match_l = [-1] * n_left
      match_r = [-1] * n_right
      matching = 0
      INF = n_left + 1
  
      while True:
          # BFS layering
          dist = [-1] * n_left
          q = deque()
          for u in range(n_left):
              if match_l[u] == -1:
                  dist[u] = 0
                  q.append(u)
          limit = INF
          while q:
              u = q.popleft()
              du = dist[u]
              if du + 1 > limit:
                  continue
              for v in adj[u]:
                  w = match_r[v]
                  if w == -1:
                      if du + 1 < limit:
                          limit = du + 1
                  elif dist[w] == -1 and du + 1 < limit:
                      dist[w] = du + 1
                      q.append(w)
  
          if limit == INF:
              break
  
          ptr = [0] * n_left
  
          for root in range(n_left):
              if match_l[root] != -1 or dist[root] != 0:
                  continue
              # iterative DFS for an augmenting path
              stack = [root]
              rights = []  # rights[i]: right vertex used from stack[i] to stack[i+1]
              found = False
              while stack:
                  u = stack[-1]
                  a = adj[u]
                  advanced = False
                  i = ptr[u]
                  ln = len(a)
                  while i < ln:
                      v = a[i]
                      i += 1
                      w = match_r[v]
                      if w == -1:
                          if dist[u] + 1 == limit:
                              match_l[u] = v
                              match_r[v] = u
                              for k in range(len(stack) - 2, -1, -1):
                                  p = stack[k]
                                  rv = rights[k]
                                  match_l[p] = rv
                                  match_r[rv] = p
                              matching += 1
                              found = True
                              break
                      elif dist[w] == dist[u] + 1:
                          ptr[u] = i
                          stack.append(w)
                          rights.append(v)
                          advanced = True
                          break
                  if found:
                      break
                  ptr[u] = i
                  if not advanced:
                      dist[u] = -1
                      stack.pop()
                      if rights:
                          rights.pop()
  
      return matching

• #3DeepSeek V4 Pro 0423不正解 · 9 / 11 件のテストにパス回答時間 2.8 秒 · 実行時間 1.2 秒 · $0.0006

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 実行制限時間を超過しました⏱ 実行制限時間を超過しました
  コード

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency list for left side
      graph = [[] for _ in range(n_left)]
      for u, v in edges:
          graph[u].append(v)
  
      # matchR[v] = u if job v is matched to worker u, else -1
      matchR = [-1] * n_right
  
      # Standard DFS for augmenting path (Kuhn's algorithm)
      def dfs(u, seen):
          for v in graph[u]:
              if seen[v]:
                  continue
              seen[v] = True
              if matchR[v] == -1 or dfs(matchR[v], seen):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          # seen array for this DFS iteration
          seen = [False] * n_right
          if dfs(u, seen):
              result += 1
  
      return result

  2回目の試行

  不正解 · 10 / 11 件のテストにパス回答時間 7.5 秒 · $0.0013

  モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 実行制限時間を超過しました⏱ 60 ms

  コード

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency (remove duplicates per worker)
      graph = [set() for _ in range(n_left)]
      for u, v in edges:
          graph[u].add(v)
      graph = [list(adj) for adj in graph]
  
      matchR = [-1] * n_right
  
      # DFS with pointer for visited tracking using iteration counter
      visited = [0] * n_right
      visit_counter = 0
  
      def dfs(u):
          nonlocal visit_counter
          for v in graph[u]:
              if visited[v] == visit_counter:
                  continue
              visited[v] = visit_counter
              if matchR[v] == -1 or dfs(matchR[v]):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          visit_counter += 1
          if dfs(u):
              result += 1
  
      return result

• #4Google Gemini 4 Argon不正解 · 8 / 11 件のテストにパス回答時間 10 秒 · 実行時間 3.2 秒 · $0.0080

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	2 ms

  ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ 実行制限時間を超過しました✓ 1 ms✓ <1 ms⏱ 実行制限時間を超過しました⏱ 実行制限時間を超過しました
  コード

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      dist = [0] * n_left
      INF = 10**9
  
      # Hopcroft-Karp algorithm
      while True:
          queue = deque()
          for u in range(n_left):
              if pair_u[u] == -1:
                  dist[u] = 0
                  queue.append(u)
              else:
                  dist[u] = INF
          
          found_augmenting_path = False
          while queue:
              u = queue.popleft()
              d_next = dist[u] + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      found_augmenting_path = True
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if not found_augmenting_path:
              break
              
          # Iterative DFS to avoid recursion limit and overhead
          for start_u in range(n_left):
              if pair_u[start_u] == -1:
                  stack = [(start_u, 0)]
                  while stack:
                      u, idx = stack[-1]
                      adj_u = adj[u]
                      n_adj = len(adj_u)
                      while idx < n_adj:
                          v = adj_u[idx]
                          pu = pair_v[v]
                          if pu == -1:
                              # Found augmenting path, trace back and flip edges
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                          elif dist[pu] == dist[u] + 1:
                              stack[-1] = (u, idx)
                              dist[pu] = INF  # Mark visited in this phase
                              stack.append((pu, 0))
                              break
                          idx += 1
                      else:
                          stack.pop()
                          
      return matching

  2回目の試行

  正解 · 11 / 11 件のテストにパス回答時間 17 秒 · $0.01

  モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])期待値 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])期待値 1	<1 ms

  ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 ms

  コード

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      INF = 10**9
      unmatched = [u for u in range(n_left) if pair_u[u] == -1]
  
      while unmatched:
          dist = [INF] * n_left
          for u in unmatched:
              dist[u] = 0
          
          queue = deque(unmatched)
          min_free_dist = INF
          
          while queue:
              u = queue.popleft()
              d = dist[u]
              if d >= min_free_dist:
                  continue
              d_next = d + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      min_free_dist = d_next
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if min_free_dist == INF:
              break
              
          new_unmatched = []
          for start_u in unmatched:
              stack = [(start_u, 0, 0)]
              dist[start_u] = INF
              while stack:
                  u, idx, d = stack[-1]
                  adj_u = adj[u]
                  n_adj = len(adj_u)
                  d_next = d + 1
                  while idx < n_adj:
                      v = adj_u[idx]
                      pu = pair_v[v]
                      if pu == -1:
                          if d_next == min_free_dist:
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx, _ = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                      elif dist[pu] == d_next and d_next < min_free_dist:
                          stack[-1] = (u, idx, d)
                          dist[pu] = INF
                          stack.append((pu, 0, d_next))
                          break
                      idx += 1
                  else:
                      stack.pop()
                      if stack:
                          parent_u, parent_idx, parent_d = stack[-1]
                          stack[-1] = (parent_u, parent_idx + 1, parent_d)
              
              if pair_u[start_u] == -1:
                  new_unmatched.append(start_u)
                  
          unmatched = new_unmatched
  
      return matching

トークンコスト: $0.04 · 対戦の進行と評価方法について →