結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:46:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,096 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 156,360 KB
最終ジャッジ日時 2025-03-31 17:47:53
合計ジャッジ時間 7,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    A = []
    B_pool = []
    C = []
    for _ in range(N):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        c = int(input[ptr])
        ptr += 1
        A.append(a)
        B_pool.append(b)
        C.append(c)

    # Precompute for each group the valid B indices and their max contribution
    valid_Bs_for_groups = []
    max_contributions = []
    for i in range(N):
        a = A[i]
        c = C[i]
        valid = []
        current_max = -1
        for j in range(N):
            b_j = B_pool[j]
            if b_j == a or b_j == c:
                continue
            sum_abc = a + b_j + c
            x = min(a, b_j, c)
            z = max(a, b_j, c)
            y = sum_abc - x - z
            if y == a or y == c:
                valid.append(j)
                current = max(a, b_j, c)
                if current > current_max:
                    current_max = current
        if not valid:
            print("NO")
            return
        valid_Bs_for_groups.append(valid)
        max_contributions.append(current_max)

    # Build the bipartite graph adjacency list
    graph = [[] for _ in range(N)]
    for i in range(N):
        graph[i] = valid_Bs_for_groups[i]

    # Hopcroft-Karp algorithm to find maximum matching
    def hopcroft_karp():
        pair_u = [-1] * N
        pair_v = [-1] * N
        dist = [0] * N

        def bfs():
            queue = deque()
            for u in range(N):
                if pair_u[u] == -1:
                    dist[u] = 0
                    queue.append(u)
                else:
                    dist[u] = float('inf')
            dist_null = float('inf')
            while queue:
                u = queue.popleft()
                if dist[u] < dist_null:
                    for v in graph[u]:
                        if pair_v[v] == -1:
                            dist_null = dist[u] + 1
                        elif dist[pair_v[v]] == float('inf'):
                            dist[pair_v[v]] = dist[u] + 1
                            queue.append(pair_v[v])
            return dist_null != float('inf')

        def dfs(u):
            for v in graph[u]:
                if pair_v[v] == -1 or (dist[pair_v[v]] == dist[u] + 1 and dfs(pair_v[v])):
                    pair_u[u] = v
                    pair_v[v] = u
                    return True
            dist[u] = float('inf')
            return False

        result = 0
        while bfs():
            for u in range(N):
                if pair_u[u] == -1:
                    if dfs(u):
                        result += 1
        return result

    max_matching = hopcroft_karp()
    if max_matching != N:
        print("NO")
        return

    S_max = sum(max_contributions)
    if S_max >= M:
        print("YES")
        print("KADOMATSU!")
    else:
        print("YES")
        print("NO")

if __name__ == "__main__":
    main()
0