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

Heaviest independent set in a tree

def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:

max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])  # -> 5
max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])  # -> 6

• #1Google Gemini 3.8 Flash正解 · 11 / 11 件のテストにパス回答時間 3.9 秒 · 実行時間 1.6 秒 · $0.0020

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])期待値 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])期待値 6	<1 ms

  ✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 755 ms⏱ 796 ms
  コード

  import sys
  
  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 0:
          return 0
      if n == 1:
          return max(0, weights[0])
      
      adj = [[] for _ in range(n)]
      for u, v in edges:
          adj[u].append(v)
          adj[v].append(u)
          
      order = [0] * n
      parent = [-1] * n
      visited = [False] * n
      
      # BFS to get topological order
      visited[0] = True
      head = 0
      tail = 1
      order[0] = 0
      
      while head < tail:
          u = order[head]
          head += 1
          for v in adj[u]:
              if not visited[v]:
                  visited[v] = True
                  parent[v] = u
                  order[tail] = v
                  tail += 1
                  
      # dp[u][0] = max weight in subtree u if u is NOT chosen
      # dp[u][1] = max weight in subtree u if u IS chosen
      dp0 = [0] * n
      dp1 = [0] * n
      
      for i in range(n):
          dp1[i] = weights[i]
          
      for i in range(n - 1, -1, -1):
          u = order[i]
          # In case u has negative weight, choosing u gives weights[u] plus children's not-chosen dp
          p = parent[u]
          if p != -1:
              dp0[p] += max(dp0[u], dp1[u])
              dp1[p] += dp0[u]
              
      ans = max(0, dp0[0], dp1[0])
      return ans

• #1OpenAI GPT-5.3-Codex正解 · 11 / 11 件のテストにパス回答時間 3.5 秒 · 実行時間 1.6 秒 · $0.0049

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])期待値 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])期待値 6	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 808 ms⏱ 782 ms
  コード

  from typing import List
  
  def max_independent_set(n: int, edges: List[List[int]], weights: List[int]) -> int:
      if n <= 0:
          return 0
      g = [[] for _ in range(n)]
      for u, v in edges:
          g[u].append(v)
          g[v].append(u)
  
      parent = [-1] * n
      order = []
      stack = [0]
      parent[0] = 0
  
      while stack:
          u = stack.pop()
          order.append(u)
          for v in g[u]:
              if parent[v] == -1:
                  parent[v] = u
                  stack.append(v)
  
      dp0 = [0] * n  # best if node not chosen
      dp1 = [0] * n  # best if node chosen
  
      for u in reversed(order):
          take = weights[u]
          skip = 0
          for v in g[u]:
              if v == parent[u]:
                  continue
              take += dp0[v]
              skip += dp0[v] if dp0[v] >= dp1[v] else dp1[v]
          dp1[u] = take
          dp0[u] = skip
  
      ans = dp0[0] if dp0[0] >= dp1[0] else dp1[0]
      return ans if ans > 0 else 0

• #1Mistral Devstral 2 2512正解 · 11 / 11 件のテストにパス回答時間 1.4 秒 · 実行時間 1.9 秒 · $0.0007

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])期待値 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])期待値 6	<1 ms

  ✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.0 秒⏱ 830 ms
  コード

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      from collections import deque
  
      if n == 0:
          return 0
  
      adj = [[] for _ in range(n)]
      for u, v in edges:
          adj[u].append(v)
          adj[v].append(u)
  
      parent = [-1] * n
      root = 0
      q = deque([root])
      parent[root] = -1
      order = []
      while q:
          u = q.popleft()
          order.append(u)
          for v in adj[u]:
              if parent[v] == -1 and v != parent[u]:
                  parent[v] = u
                  q.append(v)
  
      dp_include = [0] * n
      dp_exclude = [0] * n
  
      for u in reversed(order):
          include = weights[u]
          exclude = 0
          for v in adj[u]:
              if v == parent[u]:
                  continue
              include += dp_exclude[v]
              exclude += max(dp_include[v], dp_exclude[v])
          dp_include[u] = include
          dp_exclude[u] = exclude
  
      return max(dp_include[root], dp_exclude[root])

• #4Z.ai GLM 5.3不正解 · 4 / 11 件のテストにパス回答時間 2.7 秒 · 実行時間 1.3 秒 · $0.0008

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])期待値 5出力値 1	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])期待値 6出力値 5	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✗ 不正解✗ 不正解✗ 不正解⏱ 不正解⏱ 不正解
  コード

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 1:
          return max(0, weights[0])
      adj = [[] for _ in range(n)]
      for a, b in edges:
          adj[a].append(b)
          adj[b].append(a)
      taken = [False] * n
      parent = [0] * n
      order = [0] * n
      order[0] = 0
      taken[0] = True
      head = 0
      cnt = 1
      while head < cnt:
          u = order[head]
          head += 1
          pu = parent[u]
          for v in adj[u]:
              if v != pu:
                  parent[v] = u
                  order[cnt] = v
                  cnt += 1
                  taken[v] = True
      dp_incl = [0] * n
      dp_excl = [0] * n
      dp_skip = [0] * n
      for i in range(n - 1, -1, -1):
          u = order[i]
          wi = weights[u]
          inc = wi if wi > 0 else 0
          if taken[u]:
              if inc:
                  dp_incl[u] = inc + dp_skip[u]
              else:
                  dp_incl[u] = 0
              dp_excl[u] = dp_skip[u]
          else:
              best = 0 if dp_incl[u] > 0 else dp_incl[u]
              if dp_excl[u] > best:
                  best = dp_excl[u]
              if inc:
                  v = inc + dp_skip[u]
                  if v > best:
                      best = v
              dp_skip[parent[u]] += best if best > 0 else 0
      r = 0
      if dp_incl[order[0]] > r:
          r = dp_incl[order[0]]
      if dp_excl[order[0]] > r:
          r = dp_excl[0]
      return r

  2回目の試行

  不正解 · 4 / 11 件のテストにパス回答時間 4.2 秒 · $0.0007

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

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])期待値 5出力値 7	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])期待値 6出力値 11	<1 ms

  ✓ <1 ms✓ <1 ms✗ 不正解✓ <1 ms✓ <1 ms✗ 不正解✗ 不正解⏱ 不正解⏱ 不正解

  コード

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 1:
          return max(0, weights[0])
      adj = [[] for _ in range(n)]
      for a, b in edges:
          adj[a].append(b)
          adj[b].append(a)
      parent = [-1] * n
      order = [0] * n
      cnt = 1
      head = 0
      while head < cnt:
          u = order[head]
          head += 1
          for v in adj[u]:
              if v != parent[u]:
                  parent[v] = u
                  order[cnt] = v
                  cnt += 1
      incl = [0] * n
      excl = [0] * n
      best = [0] * n  # best contribution to parent: max(incl, excl)
      for i in range(n - 1, -1, -1):
          u = order[i]
          w = weights[u]
          take = w + excl[u] if w > 0 else excl[u]
          if w > 0 and w + excl[u] > take:
              take = w + excl[u]
          incl[u] = (w + excl[u]) if w > 0 else excl[u]
          if incl[u] < excl[u] + (w if False else 0):
              pass
          # excl[u] already accumulated sum of best children
          incl_val = w + excl[u] if w > 0 else excl[u]
          b = incl_val if incl_val > excl[u] else excl[u]
          if b < 0:
              b = 0
          best[u] = b
          p = parent[u]
          if p >= 0:
              excl[p] += b
      root = order[0]
      res = max(incl[root], excl[root], 0)
      return res

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