結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0