結果

問題 No.640 76本のトロンボーン
ユーザー gew1fw
提出日時 2025-06-12 18:58:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,185 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 81,856 KB
実行使用メモリ 71,144 KB
最終ジャッジ日時 2025-06-12 18:58:11
合計ジャッジ時間 1,950 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    N = int(input())
    grid = [input().strip() for _ in range(N)]

    # For each column, find all possible vertical trombone ranges (1-based)
    vert_available = []  # vert_available[c] is list of (start, end) for column c (0-based)
    for c in range(N):
        ranges = []
        max_i = N - (N - 1)
        for i in range(max_i):
            start_row = i + 1  # 1-based
            end_row = start_row + (N - 1) - 1
            valid = True
            for row in range(start_row - 1, end_row):  # convert to 0-based
                if row >= N or grid[row][c] == '#':
                    valid = False
                    break
            if valid:
                ranges.append((start_row, end_row))
        vert_available.append(ranges)
    C = [c for c in range(N) if vert_available[c]]

    # For each row, find all possible horizontal trombone ranges (1-based)
    horiz_available = []  # horiz_available[r] is list of (start, end) for row r (0-based)
    for r in range(N):
        ranges = []
        max_j = N - (N - 1)
        for j in range(max_j):
            start_col = j + 1  # 1-based
            end_col = start_col + (N - 1) - 1
            valid = True
            for col in range(start_col - 1, end_col):  # convert to 0-based
                if col >= N or grid[r][col] == '#':
                    valid = False
                    break
            if valid:
                ranges.append((start_col, end_col))
        horiz_available.append(ranges)
    R = [r for r in range(N) if horiz_available[r]]

    # Build edges between columns in C and rows in R if they intersect
    edges = []
    for c in C:
        for r in R:
            # Check if row r+1 (1-based) is in any vertical range of column c
            current_r_1based = r + 1
            in_vert = False
            for (start, end) in vert_available[c]:
                if start <= current_r_1based <= end:
                    in_vert = True
                    break
            if not in_vert:
                continue
            # Check if column c+1 (1-based) is in any horizontal range of row r
            current_c_1based = c + 1
            in_horiz = False
            for (start, end) in horiz_available[r]:
                if start <= current_c_1based <= end:
                    in_horiz = True
                    break
            if in_horiz:
                edges.append((c, r))

    # Build adjacency list for bipartite graph
    graph = {c: [] for c in C}
    for c, r in edges:
        graph[c].append(r)

    # Hopcroft-Karp algorithm implementation
    def hopcroft_karp():
        pair_U = {u: None for u in C}
        pair_V = {v: None for v in R}
        dist = {}

        def bfs():
            queue = deque()
            for u in C:
                if pair_U[u] is None:
                    dist[u] = 0
                    queue.append(u)
                else:
                    dist[u] = float('inf')
            dist[None] = float('inf')
            while queue:
                u = queue.popleft()
                if u is not None:
                    for v in graph[u]:
                        if dist.get(pair_V.get(v, None), float('inf')) == float('inf'):
                            dist[pair_V.get(v, None)] = dist[u] + 1
                            queue.append(pair_V.get(v, None))
            return dist.get(None, float('inf')) != float('inf')

        def dfs(u):
            if u is not None:
                for v in graph[u]:
                    if dist.get(pair_V.get(v, None), float('inf')) == dist[u] + 1:
                        if dfs(pair_V.get(v, None)):
                            pair_U[u] = v
                            pair_V[v] = u
                            return True
                dist[u] = float('inf')
                return False
            return True

        result = 0
        while bfs():
            for u in C:
                if pair_U[u] is None:
                    if dfs(u):
                        result += 1
        return result

    max_matching = hopcroft_karp()
    X = len(C) + len(R) - max_matching
    print(X)

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