結果

問題 No.640 76本のトロンボーン
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:59:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,615 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 67,628 KB
最終ジャッジ日時 2025-03-26 15:59:53
合計ジャッジ時間 1,867 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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)]

    # 縦方向のトロンボーン候補を集める
    vertical = []
    vertical_cols = []  # (col, i_start)
    for col in range(N):
        # 可能なi_startを探す。各列colに対して、縦方向に配置可能なi_startをリストする
        possible = []
        max_len = N-1
        for i_start in range(N - max_len + 1):
            ok = True
            for di in range(max_len):
                if grid[i_start + di][col] != '.':
                    ok = False
                    break
            if ok:
                possible.append(i_start)
        # 最も上のi_startを選ぶ
        if possible:
            # i_startは可能な中で最小のもの（最も上）
            i_start = possible[0]
            vertical_cols.append( (col, i_start) )
    A = len(vertical_cols)
    # 各縦トロンボーンの行範囲を記録
    vertical_ranges = []
    for col, i_start in vertical_cols:
        i_end = i_start + (N-1) - 1
        vertical_ranges.append( (col, i_start, i_end) )

    # 横方向のトロンボーン候補を集める
    horizontal = []
    for row in range(N):
        # 可能なj_startをすべて列挙
        intervals = []
        max_width = N-1
        for j_start in range(N - max_width +1):
            ok = True
            for dj in range(max_width):
                if grid[row][j_start + dj] != '.':
                    ok = False
                    break
            if ok:
                intervals.append( (j_start, j_start + max_width -1) )
        # 区間スケジューリングで最大数を選ぶ
        intervals.sort(key=lambda x: x[1])  # 終了位置でソート
        selected = []
        last_end = -1
        for start, end in intervals:
            if start > last_end:
                selected.append( (start, end) )
                last_end = end
        # 各selectedのj_startはstart
        for start, end in selected:
            horizontal.append( (row, start) )
    B = len(horizontal)
    # 各横トロンボーンの列範囲を記録
    horizontal_ranges = []
    for row, j_start in horizontal:
        j_end = j_start + (N-1) -1
        horizontal_ranges.append( (row, j_start, j_end) )

    # 二部グラフを構築: vertical_ranges vs horizontal_ranges
    # 左側がvertical (A個)、右側がhorizontal (B個)
    # 交差する場合に辺を張る
    # 交差条件: verticalのcolが横のj_start <= col <= j_end
    #           horizontalのrowが縦のi_start <= row <= i_end
    edges = [[] for _ in range(A)]
    for v_idx in range(A):
        v_col, v_i_start, v_i_end = vertical_ranges[v_idx]
        for h_idx in range(B):
            h_row, h_j_start, h_j_end = horizontal_ranges[h_idx]
            # v_colが [h_j_start, h_j_end] の範囲内かつ h_rowが [v_i_start, v_i_end] の範囲内か？
            if h_j_start <= v_col <= h_j_end and v_i_start <= h_row <= v_i_end:
                edges[v_idx].append(h_idx)

    # 最大マッチングを求める (Hopcroft-Karp)
    def hopcroft_karp():
        pair_u = [-1] * A
        pair_v = [-1] * B
        dist = [0] * A

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

    M = hopcroft_karp()
    print(A + B - M)

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