#1059695 (PyPy3) No.640 76本のトロンボーン

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX