結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    # Generate all possible horizontal trombones
    H = []
    for i in range(n):
        max_j = n - (n-1)  # because j can be from 0 to max_j-1 inclusive
        for j in range(max_j):
            valid = True
            for k in range(n-1):
                if j + k >= n:
                    valid = False
                    break
                if grid[i][j + k] != '.':
                    valid = False
                    break
            if valid:
                H.append((i, j))

    # Generate all possible vertical trombones
    V = []
    for j in range(n):
        max_i = n - (n-1)
        for i in range(max_i):
            valid = True
            for k in range(n-1):
                if i + k >= n:
                    valid = False
                    break
                if grid[i + k][j] != '.':
                    valid = False
                    break
            if valid:
                V.append((i, j))

    # Precompute the areas for each trombone
    h_areas = []
    for (i, j) in H:
        area = set()
        for k in range(n-1):
            area.add((i, j + k))
        h_areas.append(area)

    v_areas = []
    for (i, j) in V:
        area = set()
        for k in range(n-1):
            area.add((i + k, j))
        v_areas.append(area)

    # Build the bipartite graph
    graph = [[] for _ in range(len(H))]
    for h_idx in range(len(H)):
        h_area = h_areas[h_idx]
        for v_idx in range(len(V)):
            v_area = v_areas[v_idx]
            if len(h_area.intersection(v_area)) > 0:
                graph[h_idx].append(v_idx)

    # Hopcroft-Karp algorithm implementation
    def hopcroft_karp():
        pair_U = [-1] * len(H)
        pair_V = [-1] * len(V)
        dist = [0] * len(H)

        def bfs():
            queue = deque()
            for u in range(len(H)):
                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(len(H)):
                if pair_U[u] == -1:
                    if dfs(u):
                        result += 1
        return result

    max_matching = hopcroft_karp()
    max_independent_set = len(H) + len(V) - max_matching
    print(max_independent_set)

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