結果

問題 No.640 76本のトロンボーン
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:41:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,007 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 66,944 KB
最終ジャッジ日時 2025-06-12 14:42:13
合計ジャッジ時間 1,833 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 2 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline().strip())
    grid = []
    for _ in range(N):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    # Build bipartite graph
    # Rows are numbered 0..N-1, columns 0..N-1
    # Edges from rows to columns for horizontal trombones
    # Edges from columns to rows for vertical trombones
    graph = [[] for _ in range(2 * N)]  # 0..N-1 are rows, N..2N-1 are columns

    # Add edges for horizontal trombones
    for i in range(N):
        for j in [0, 1]:
            valid = True
            for k in range(j, j + (N-1)):
                if k >= N:
                    valid = False
                    break
                if grid[i][k] != '.':
                    valid = False
                    break
            if valid:
                for k in range(j, j + (N-1)):
                    graph[i].append(N + k)
    
    # Add edges for vertical trombones
    for j in range(N):
        for i in [0, 1]:
            valid = True
            for k in range(i, i + (N-1)):
                if k >= N:
                    valid = False
                    break
                if grid[k][j] != '.':
                    valid = False
                    break
            if valid:
                for k in range(i, i + (N-1)):
                    graph[N + j].append(k)
    
    # Compute maximum bipartite matching using Hopcroft-Karp algorithm
    def hopcroft_karp():
        pair_u = [-1] * (2 * N)
        pair_v = [-1] * (2 * N)
        dist = [0] * (2 * 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_found = float('inf')
            while queue:
                u = queue.popleft()
                if dist[u] < dist_found:
                    for v in graph[u]:
                        if pair_v[v] == -1:
                            dist_found = dist[u] + 1
                        elif dist[pair_v[v]] == float('inf'):
                            dist[pair_v[v]] = dist[u] + 1
                            queue.append(pair_v[v])
            return dist_found != 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()
    max_x = 2 * N - max_matching
    print(max_x)

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