結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:22:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,649 bytes |
コンパイル時間 | 331 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 157,824 KB |
最終ジャッジ日時 | 2025-06-12 21:25:05 |
合計ジャッジ時間 | 6,539 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 5 TLE * 1 -- * 8 |
ソースコード
import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N, M = map(int, sys.stdin.readline().split()) triplets = [] B_list = [] for _ in range(N): A, B, C = map(int, sys.stdin.readline().split()) triplets.append((A, B, C)) B_list.append(B) # Precompute allowed B's for each triplet allowed = [[] for _ in range(N)] for i in range(N): A, B, C = triplets[i] for j in range(N): B_j = B_list[j] if B_j == A or B_j == C: continue s = sorted([A, B_j, C]) if s[1] not in {A, C}: continue allowed[i].append(j) if not allowed[i]: print("NO") return # Bipartite graph: left nodes are triplets (0..N-1), right nodes are B indices (0..N-1) # Each edge (i -> j) exists if j is allowed for i. # Hopcroft-Karp algorithm for maximum bipartite matching class HopcroftKarp: def __init__(self, graph, U, V): self.graph = graph # adjacency list: for u in U, graph[u] is list of v in V self.U = U self.V = V self.pair_U = [-1] * U self.pair_V = [-1] * V self.dist = [0] * U def bfs(self): queue = deque() for u in range(self.U): if self.pair_U[u] == -1: self.dist[u] = 0 queue.append(u) else: self.dist[u] = float('inf') self.dist_found = float('inf') while queue: u = queue.popleft() if self.dist[u] < self.dist_found: for v in self.graph[u]: if self.pair_V[v] == -1: self.dist_found = self.dist[u] + 1 elif self.dist[self.pair_V[v]] == float('inf'): self.dist[self.pair_V[v]] = self.dist[u] + 1 queue.append(self.pair_V[v]) return self.dist_found != float('inf') def dfs(self, u): for v in self.graph[u]: if self.pair_V[v] == -1 or (self.dist[self.pair_V[v]] == self.dist[u] + 1 and self.dfs(self.pair_V[v])): self.pair_U[u] = v self.pair_V[v] = u return True self.dist[u] = float('inf') return False def max_matching(self): result = 0 while self.bfs(): for u in range(self.U): if self.pair_U[u] == -1: if self.dfs(u): result += 1 return result graph = [[] for _ in range(N)] for i in range(N): for j in allowed[i]: graph[i].append(j) hk = HopcroftKarp(graph, N, N) max_match = hk.max_matching() if max_match != N: print("NO") return # Now, compute maximum sum of max(A_i, B_j, C_i) for each triplet i assigned B_j # For each i, for each allowed j, compute the max weight = [[0] * N for _ in range(N)] for i in range(N): A, _, C = triplets[i] for j in allowed[i]: B_j = B_list[j] max_val = max(A, B_j, C) weight[i][j] = max_val # Now, model this as a maximum weight bipartite matching problem # We need to find a permutation p where p is a matching, and sum weight[i][p[i]] is maximized # Since it's a maximum weight bipartite matching, we can use the Hungarian algorithm def hungarian(matrix): n = len(matrix) m = len(matrix[0]) u = [0] * (n + 1) v = [0] * (m + 1) p = [0] * (m + 1) way = [0] * (m + 1) for i in range(1, n+1): p[0] = i minv = [float('inf')] * (m+1) used = [False] * (m+1) j0 = 0 i0 = i delta = 0 while True: used[j0] = True i0 = p[j0] delta = float('inf') j1 = 0 for j in range(1, m+1): if not used[j]: cur = matrix[i0-1][j-1] - u[i0] - v[j] if cur < minv[j]: minv[j] = cur way[j] = j0 if minv[j] < delta: delta = minv[j] j1 = j for j in range(m+1): if used[j]: u[p[j]] += delta v[j] -= delta else: minv[j] -= delta j0 = j1 if p[j0] == 0: break while True: j1 = way[j0] p[j0] = p[j1] j0 = j1 if j0 == 0: break return -v[0] # Create the cost matrix for the Hungarian algorithm # Since the Hungarian algorithm minimizes the cost, we'll use negative weights cost = [] for i in range(N): row = [] for j in range(N): if j in allowed[i]: row.append(-weight[i][j]) else: row.append(float('inf')) cost.append(row) max_sum = -hungarian(cost) if max_sum >= M: print("YES") print("KADOMATSU!") else: print("YES") print("NO") if __name__ == '__main__': main()