結果

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

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    grid = []
    for _ in range(N):
        line = sys.stdin.readline().strip()
        grid.append(list(line))
    
    # Generate H trombones
    h = []
    for i in range(N):
        max_j = N - (N-1)
        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 V 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((j, i))
    
    # Preprocess V into columns
    v_list = []
    for (j, i) in v:
        i_end = i + (N-2)
        v_list.append((j, i, i_end))
    
    v_col = defaultdict(list)
    for idx, (j, i, i_end) in enumerate(v_list):
        v_col[j].append((i, i_end, idx))
    
    # Build adjacency list
    H = len(h)
    V = len(v)
    adj = [[] for _ in range(H)]
    for H_idx, (i_h, j_h) in enumerate(h):
        h_len = N-1
        for k in range(j_h, j_h + h_len):
            if k >= N:
                continue
            if k not in v_col:
                continue
            vs = v_col[k]
            for (i_v, i_v_end, v_idx) in vs:
                if i_v <= i_h <= i_v_end:
                    adj[H_idx].append(v_idx)
    
    # Hopcroft-Karp algorithm
    pair_U = [-1] * H
    pair_V = [-1] * V
    dist = [0] * H
    
    def bfs():
        queue = deque()
        for u in range(H):
            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 adj[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 adj[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(H):
            if pair_U[u] == -1:
                if dfs(u):
                    result += 1
    X = (H + V) - result
    print(X)

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