結果
| 問題 | No.3539 Parentheses Square |
| コンテスト | |
| ユーザー |
 もの
|
| 提出日時 | 2026-03-04 23:25:09 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 27,605 bytes |
| 記録 | |
| コンパイル時間 | 364 ms |
| コンパイル使用メモリ | 85,252 KB |
| 実行使用メモリ | 126,788 KB |
| 最終ジャッジ日時 | 2026-05-08 20:52:59 |
| 合計ジャッジ時間 | 8,231 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 TLE * 1 -- * 34 |
ソースコード
############################################################################################
import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,random
from decimal import Decimal
from typing import List, Optional, Tuple
import sys
def I() -> str:
"""
標準入力から1行読み取る（改行なし）
Returns:
入力された文字列
"""
return input()
def IS():
"""
標準入力から1行読み取り、空白で分割する
Returns:
分割された文字列のリスト
"""
return input().split()
def II() -> int:
"""
標準入力から整数を1つ読み取る
Returns:
入力された整数
"""
return int(input())
def IIS():
"""
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
使い方:
a, b = IIS() # 2つの整数を受け取る
arr = IIS() # 任意個の整数をリストで受け取る
"""
return list(map(int, input().split()))
def LIIS():
"""
IIS() のエイリアス
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
"""
return list(map(int, input().split()))
"""
べき乗の高速計算・逆元の計算
機能:
- 繰り返し二乗法による高速なべき乗計算 O(log N)
- 逆元の計算（フェルマーの小定理） O(log mod)
- 逆元の計算（拡張ユークリッドの互除法） O(log min(a, mod))
- 組み合わせ計算（mod込み）
使い方:
# べき乗
pow_mod(2, 10, 1000000007) # 2^10 mod 10^9+7
# 逆元
inv = mod_inverse(3, 1000000007) # 3の逆元 mod 10^9+7
# 組み合わせ
comb = Combination(10**6, 10**9+7)
print(comb.nCr(10, 3)) # 10C3
"""
from typing import Tuple
def pow_mod(a: int, n: int, mod: int) -> int:
"""a^n mod mod を高速に計算する（繰り返し二乗法）
Args:
a: 底
n: 指数
mod: 法
Returns:
a^n mod mod
計算量: O(log N)
"""
result = 1
a %= mod
while n > 0:
if n & 1:
result = (result * a) % mod
a = (a * a) % mod
n >>= 1
return result
def mod_inverse_fermat(a: int, mod: int) -> int:
"""フェルマーの小定理による逆元の計算
mod が素数の場合に使用可能
a^(-1) ≡ a^(mod-2) (mod mod)
Args:
a: 逆元を求める数
mod: 法（素数）
Returns:
a の逆元 mod mod
計算量: O(log mod)
"""
return pow_mod(a, mod - 2, mod)
def extgcd(a: int, b: int) -> Tuple[int, int, int]:
"""拡張ユークリッドの互除法
ax + by = gcd(a, b) を満たす x, y を求める
Args:
a, b: 整数
Returns:
(gcd(a, b), x, y)
計算量: O(log min(a, b))
"""
if b == 0:
return a, 1, 0
g, x, y = extgcd(b, a % b)
return g, y, x - (a // b) * y
def mod_inverse_extgcd(a: int, mod: int) -> int:
"""拡張ユークリッドの互除法による逆元の計算
mod が素数でなくても使用可能（gcd(a, mod) = 1 が必要）
Args:
a: 逆元を求める数
mod: 法
Returns:
a の逆元 mod mod（存在しない場合は -1）
計算量: O(log min(a, mod))
"""
g, x, _ = extgcd(a, mod)
if g != 1:
return -1 # 逆元が存在しない
return x % mod
class Combination:
"""組み合わせ計算（mod 込み）
階乗と逆元を前計算して高速に nCr を計算する
"""
def __init__(self, n: int, mod: int):
"""
Args:
n: 計算する組み合わせの最大値
mod: 法（素数）
計算量: O(N)
"""
self.n = n
self.mod = mod
# 階乗を前計算
self.fact = [1] * (n + 1)
for i in range(1, n + 1):
self.fact[i] = (self.fact[i - 1] * i) % mod
# 逆元を前計算
self.inv_fact = [1] * (n + 1)
self.inv_fact[n] = mod_inverse_fermat(self.fact[n], mod)
for i in range(n - 1, -1, -1):
self.inv_fact[i] = (self.inv_fact[i + 1] * (i + 1)) % mod
def nCr(self, n: int, r: int) -> int:
"""nCr mod mod を計算する
Args:
n, r: 組み合わせのパラメータ
Returns:
nCr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[r] % self.mod *
self.inv_fact[n - r] % self.mod)
def nPr(self, n: int, r: int) -> int:
"""nPr mod mod を計算する（順列）
Args:
n, r: 順列のパラメータ
Returns:
nPr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[n - r] % self.mod)
def nHr(self, n: int, r: int) -> int:
"""重複組み合わせ nHr = (n+r-1)Cr
Args:
n, r: パラメータ
Returns:
nHr mod mod
計算量: O(1)
"""
return self.nCr(n + r - 1, r)
# def make_divisors(n: int) -> list[int]:
# """整数 n の約数をすべて列挙する
# Args:
# n: 約数を列挙する整数（n >= 1）
# Returns:
# n の約数のリスト（昇順）
# 計算量: O(√N)
# """
# lower_divisors = []
# upper_divisors = []
# i = 1
# while i * i <= n:
# if n % i == 0:
# lower_divisors.append(i)
# if i != n // i:
# upper_divisors.append(n // i)
# i += 1
# return lower_divisors + upper_divisors[::-1]
# sys.setrecursionlimit(10**7)
alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def bit_count(x):
return bin(x).count("1")
def yesno(f):
if f:print("Yes")
else:print("No")
MOD=998244353
from functools import lru_cache
INF=10**18
# import pypyjit
# pypyjit.set_param("trace_limit=24000,vec=1")
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import deque
from typing import List, Tuple
import heapq
class MaxFlow:
"""最大流アルゴリズム（Dinic法）"""
def __init__(self, n: int):
"""
Args:
n: 頂点数
"""
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, cap: int):
"""辺を追加する（u → v に容量capの辺）"""
self.graph[u].append([v, cap, len(self.graph[v])])
self.graph[v].append([u, 0, len(self.graph[u]) - 1])
def bfs(self, s: int, t: int) -> bool:
"""BFSでレベルグラフを構築する"""
self.level = [-1] * self.n
self.level[s] = 0
queue = deque([s])
while queue:
v = queue.popleft()
for to, cap, _ in self.graph[v]:
if cap > 0 and self.level[to] < 0:
self.level[to] = self.level[v] + 1
queue.append(to)
return self.level[t] >= 0
def dfs(self, v: int, t: int, f: int) -> int:
"""DFSで増加パスを見つけて流す"""
if v == t:
return f
for i in range(self.iter[v], len(self.graph[v])):
self.iter[v] = i
to, cap, rev = self.graph[v][i]
if cap > 0 and self.level[v] < self.level[to]:
d = self.dfs(to, t, min(f, cap))
if d > 0:
self.graph[v][i][1] -= d
self.graph[to][rev][1] += d
return d
return 0
def max_flow(self, s: int, t: int) -> int:
"""最大流を求める
Args:
s: 始点
t: 終点
Returns:
最大流量
"""
flow = 0
while self.bfs(s, t):
self.iter = [0] * self.n
while True:
f = self.dfs(s, t, float('inf'))
if f == 0:
break
flow += f
return flow
def min_cut(self, s: int) -> List[int]:
"""最小カットに含まれる頂点のリストを返す（始点側）
max_flow実行後に呼び出す。
"""
visited = [False] * self.n
queue = deque([s])
visited[s] = True
while queue:
v = queue.popleft()
for to, cap, _ in self.graph[v]:
if cap > 0 and not visited[to]:
visited[to] = True
queue.append(to)
return [i for i in range(self.n) if visited[i]]
class MinCostFlow:
"""最小費用流アルゴリズム（ダイクストラ法 + ポテンシャル）"""
def __init__(self, n: int):
"""
Args:
n: 頂点数
"""
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int, cap: int, cost: int):
"""辺を追加する（u → v に容量cap、コストcostの辺）"""
self.graph[u].append([v, cap, cost, len(self.graph[v])])
self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])
def min_cost_flow(self, s: int, t: int, max_flow: int) -> Tuple[int, int]:
"""最小費用流を求める
Args:
s: 始点
t: 終点
max_flow: 流す流量の上限
Returns:
(流量, 最小費用) のタプル
"""
res = 0
flow = 0
h = [0] * self.n
while flow < max_flow:
# ダイクストラ法で最短路を探す
dist = [float('inf')] * self.n
dist[s] = 0
prev_v = [-1] * self.n
prev_e = [-1] * self.n
pq = [(0, s)]
while pq:
d, v = heapq.heappop(pq)
if dist[v] < d:
continue
for i, (to, cap, cost, _) in enumerate(self.graph[v]):
if cap > 0 and dist[to] > dist[v] + cost + h[v] - h[to]:
dist[to] = dist[v] + cost + h[v] - h[to]
prev_v[to] = v
prev_e[to] = i
heapq.heappush(pq, (dist[to], to))
if dist[t] == float('inf'):
break
# ポテンシャルを更新
for v in range(self.n):
if dist[v] < float('inf'):
h[v] += dist[v]
# 流せる量を計算
d = max_flow - flow
v = t
while v != s:
d = min(d, self.graph[prev_v[v]][prev_e[v]][1])
v = prev_v[v]
# 流す
flow += d
res += d * h[t]
v = t
while v != s:
e = prev_e[v]
self.graph[prev_v[v]][e][1] -= d
rev = self.graph[prev_v[v]][e][3]
self.graph[v][rev][1] += d
v = prev_v[v]
return flow, res
class BipartiteMatching:
"""二部グラフの最大マッチング（Hopcroft-Karp: O(E√V)）"""
INF = float('inf')
def __init__(self, n: int, m: int):
self.n = n
self.m = m
self.graph = [[] for _ in range(n)]
self.match_right = [-1] * m
self.match_left = [-1] * n
self.dist_left = [0] * n # 左頂点の BFS 距離
def add_edge(self, u: int, v: int):
self.graph[u].append(v)
def _bfs(self) -> bool:
"""フェーズ開始時に最短増加パスの距離層を構築"""
queue = deque()
for v in range(self.n):
if self.match_left[v] == -1:
self.dist_left[v] = 0
queue.append(v)
else:
self.dist_left[v] = self.INF
found = False
while queue:
v = queue.popleft()
for to in self.graph[v]:
nxt = self.match_right[to]
if nxt == -1:
found = True
elif self.dist_left[nxt] == self.INF:
self.dist_left[nxt] = self.dist_left[v] + 1
queue.append(nxt)
return found
def _dfs(self, v: int) -> bool:
"""距離層に沿って増加パスを探す（使用済み辺を削除して再探索を防ぐ）"""
for to in self.graph[v]:
nxt = self.match_right[to]
if nxt == -1 or (
self.dist_left[nxt] == self.dist_left[v] + 1
and self._dfs(nxt)
):
self.match_right[to] = v
self.match_left[v] = to
return True
# この頂点からはもう増加パスなし → 距離を無効化して再訪を防ぐ
self.dist_left[v] = self.INF
return False
def max_matching(self) -> int:
res = 0
while self._bfs(): # √V 回程度で終了
for v in range(self.n):
if self.match_left[v] == -1 and self._dfs(v):
res += 1
return res
def get_matching(self) -> List[Tuple[int, int]]:
return [
(self.match_right[v], v)
for v in range(self.m)
if self.match_right[v] != -1
]
class MinVertexCover:
"""二部グラフの最小点被覆（ケーニッヒの定理）"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.matching = BipartiteMatching(n, m)
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.matching.add_edge(u, v)
def min_vertex_cover(self) -> Tuple[int, List[int], List[int]]:
"""最小点被覆を求める
Returns:
(最小点被覆数, 左側の頂点リスト, 右側の頂点リスト)
"""
max_match = self.matching.max_matching()
visited_left = [False] * self.n
visited_right = [False] * self.m
# マッチングされていない左側の頂点からDFS
def dfs(v: int):
if visited_left[v]:
return
visited_left[v] = True
for to in self.matching.graph[v]:
if not visited_right[to]:
visited_right[to] = True
if self.matching.match_right[to] != -1:
dfs(self.matching.match_right[to])
for v in range(self.n):
if self.matching.match_left[v] == -1:
dfs(v)
# 最小点被覆: 訪問されなかった左側 + 訪問された右側
left_cover = [v for v in range(self.n) if not visited_left[v]]
right_cover = [v for v in range(self.m) if visited_right[v]]
return max_match, left_cover, right_cover
class MaxIndependentSet:
"""二部グラフの最大独立集合"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.min_cover = MinVertexCover(n, m)
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.min_cover.add_edge(u, v)
def max_independent_set(self) -> Tuple[int, List[int], List[int]]:
"""最大独立集合を求める
Returns:
(最大独立集合数, 左側の頂点リスト, 右側の頂点リスト)
"""
cover_size, left_cover, right_cover = self.min_cover.min_vertex_cover()
left_cover_set = set(left_cover)
right_cover_set = set(right_cover)
left_independent = [v for v in range(self.n) if v not in left_cover_set]
right_independent = [v for v in range(self.m) if v not in right_cover_set]
independent_size = self.n + self.m - cover_size
return independent_size, left_independent, right_independent
class MinEdgeCover:
"""二部グラフの最小辺被覆"""
def __init__(self, n: int, m: int):
"""
Args:
n: 左側の頂点数
m: 右側の頂点数
"""
self.n = n
self.m = m
self.matching = BipartiteMatching(n, m)
self.graph = [[] for _ in range(n)]
def add_edge(self, u: int, v: int):
"""辺を追加する（左側のu → 右側のv）"""
self.matching.add_edge(u, v)
self.graph[u].append(v)
def min_edge_cover(self) -> Tuple[int, List[Tuple[int, int]]]:
"""最小辺被覆を求める
Returns:
(最小辺被覆数, 辺のリスト)
"""
max_match = self.matching.max_matching()
matching_edges = self.matching.get_matching()
matched_left = set()
matched_right = set()
for u, v in matching_edges:
matched_left.add(u)
matched_right.add(v)
edges = list(matching_edges)
# 左側の未マッチ頂点に辺を追加
for u in range(self.n):
if u not in matched_left and self.graph[u]:
edges.append((u, self.graph[u][0]))
# 右側の未マッチ頂点に辺を追加
for u in range(self.n):
for v in self.graph[u]:
if v not in matched_right:
edges.append((u, v))
matched_right.add(v)
break
return len(edges), edges
####################################################
class PrefixSum1D:
"""1次元累積和（動的拡張・遅延評価対応版）
更新時に累積和を即座に再計算せず、クエリ時に必要な範囲のみを遅延計算します。
これにより、複数回更新してから少数のクエリを行う場合に効率的です。
Args:
arr: 数値のリスト（省略可能）
mod: オプション。指定した場合、すべての計算でこの値によるモジュロ演算が適用されます
Usage:
ps = PrefixSum1D(arr) # arr: 1次元リスト
ps = PrefixSum1D(arr, mod=10**9+7) # モジュロ演算付き
ps.query(l, r) # [l, r) の合計 (0-indexed, 半開区間)
"""
__slots__ = ('n', 'arr', 'S', 'dirty_from', 'mod')
def __init__(self, arr=None, mod=None):
"""
Args:
arr: 数値のリスト（省略可能）
mod: オプション。モジュロ演算の値
"""
if arr is None:
arr = []
n = len(arr)
self.n = n
self.mod = mod
# 元の配列を保持（値の取得と更新に使用）
self.arr = list(arr)
# S[i] = arr[0] + arr[1] + ... + arr[i-1]（1-indexed）
self.S = [0] * (n + 1)
if mod is not None:
for i in range(n):
self.S[i + 1] = (self.S[i] + arr[i]) % mod
else:
for i in range(n):
self.S[i + 1] = self.S[i] + arr[i]
# 累積和が無効になっている範囲の最小インデックス（-1なら全て有効）
self.dirty_from = -1
def _rebuild_from(self, start_idx, end_idx=None):
"""
start_idx以降の累積和を再計算（内部用）
Args:
start_idx: 再計算を開始するインデックス（0-indexed）
end_idx: 再計算を終了するインデックス（0-indexed、この位置は含まない）
Noneの場合は最後まで再計算
"""
if start_idx < 0 or start_idx >= self.n:
return
if end_idx is None:
end_idx = self.n
else:
end_idx = min(end_idx, self.n)
S = self.S
arr = self.arr
mod = self.mod
if mod is not None:
for i in range(start_idx, end_idx):
S[i + 1] = (S[i] + arr[i]) % mod
else:
for i in range(start_idx, end_idx):
S[i + 1] = S[i] + arr[i]
# dirty範囲を更新
if end_idx >= self.n:
self.dirty_from = -1
else:
self.dirty_from = end_idx
def _ensure_valid(self, up_to_idx):
"""
up_to_idxまでの累積和が有効であることを保証（内部用）
Args:
up_to_idx: 保証する範囲の終端インデックス（1-indexed）
"""
if self.dirty_from != -1 and self.dirty_from < up_to_idx:
self._rebuild_from(self.dirty_from, up_to_idx)
def query(self, l, r):
"""arr[l] + arr[l+1] + ... + arr[r-1] を返す（0-indexed, 半開区間 [l, r)）
必要に応じて累積和を遅延計算します。
単一要素クエリ (長さ1) の場合は配列から直接返します。
"""
# 単一要素クエリの高速パス
if r - l == 1:
return self.arr[l]
# _ensure_validをインライン化
df = self.dirty_from
if df != -1 and df < r:
self._rebuild_from(df, r)
result = self.S[r] - self.S[l]
if self.mod is not None:
result %= self.mod
return result
def query_clamped(self, l, r):
"""arr[l] + arr[l+1] + ... + arr[r-1] を返す（0-indexed, 半開区間 [l, r)）
範囲外の指定を自動的に有効範囲に狭めます。
Args:
l: 左端インデックス（負の値や範囲外も可）
r: 右端インデックス（範囲外も可）
Returns:
指定範囲（クランプ後）の合計
Examples:
>>> ps = PrefixSum1D([1, 2, 3, 4, 5])
>>> ps.query_clamped(-10, 3) # 範囲: [0, 3)
6
>>> ps.query_clamped(2, 100) # 範囲: [2, 5)
12
>>> ps.query_clamped(-5, 100) # 範囲: [0, 5)
15
"""
# 範囲を [0, n] にクランプ
n = self.n
if l < 0: l = 0
elif l > n: l = n
if r < 0: r = 0
elif r > n: r = n
# l > r の場合は 0 を返す
if l >= r:
return 0
# 単一要素クエリの高速パス
if r - l == 1:
return self.arr[l]
# _ensure_validをインライン化
df = self.dirty_from
if df != -1 and df < r:
self._rebuild_from(df, r)
result = self.S[r] - self.S[l]
if self.mod is not None:
result %= self.mod
return result
def total(self):
"""全要素の合計を返す
必要に応じて累積和を遅延計算します。
"""
self._ensure_valid(self.n)
return self.S[self.n]
def get(self, i):
"""
i番目の要素を取得（O(1)）
Args:
i: インデックス（0-indexed）
Returns:
arr[i]の値
"""
if not 0 <= i < self.n:
raise IndexError(f"index {i} out of range [0, {self.n})")
return self.arr[i]
def __getitem__(self, i):
"""arr[i]を返す（Pythonの配列風アクセス）"""
return self.get(i)
def update(self, i, value):
"""
i番目の要素を更新（O(1) 遅延評価）
累積和の再計算を遅延させるため、この操作は即座に完了します。
実際の累積和はクエリ時に必要な範囲のみ計算されます。
Args:
i: インデックス（0-indexed）
value: 新しい値
"""
if not 0 <= i < self.n:
raise IndexError(f"index {i} out of range [0, {self.n})")
# mod適用
if self.mod is not None:
value %= self.mod
# 元の配列を更新
self.arr[i] = value
# dirty範囲を更新（まだdirtyでないか、より前のインデックスの場合）
if self.dirty_from == -1 or i < self.dirty_from:
self.dirty_from = i
def append(self, value):
"""
配列の末尾に要素を追加（O(1)）
Args:
value: 追加する値
"""
# mod適用
if self.mod is not None:
value %= self.mod
# 元の配列に追加
self.arr.append(value)
# 累積和が有効な場合のみ追加
if self.dirty_from == -1:
if self.mod is not None:
self.S.append((self.S[self.n] + value) % self.mod)
else:
self.S.append(self.S[self.n] + value)
else:
# dirtyな場合は累積和配列だけ拡張（値は後で計算）
self.S.append(0)
self.n += 1
def append_multiple(self, arr):
"""
複数の要素を一度に追加（O(len(arr))）
Args:
arr: 追加する値のリスト
"""
for value in arr:
self.append(value)
def pop(self):
"""
配列の末尾から要素を削除して返す（O(1)）
Returns:
削除した値
Raises:
IndexError: 配列が空の場合
"""
if self.n == 0:
raise IndexError("pop from empty array")
# 削除する値を取得
value = self.arr[self.n - 1]
self.arr.pop()
self.S.pop()
self.n -= 1
# dirty範囲が削除された要素を含む場合は調整
if self.dirty_from != -1 and self.dirty_from >= self.n:
self.dirty_from = -1 if self.n == 0 else self.n - 1
return value
def __len__(self):
"""配列の長さを返す"""
return self.n
def __repr__(self):
"""デバッグ用の文字列表現"""
return f"PrefixSum1D({self.arr})"
n=II()
T=[I() for i in range(n)]
li=[[] for i in range(n)]
# li2=[[] for i in range(n)]
right=[]
s=[]
cnt2=0
for i in range(n):
cnt2=0
p=[0]*n
for j in range(n):
if T[i][j]!="(":
p[j]+=1
p=PrefixSum1D(p)
def f(num,cnt):
global cnt2
if cnt2>=n:return
if num==n:
if cnt==0:
cnt2+=1
li[i].append("".join(s))
right.append("".join(s))
return
if T[i][num]!=")" and cnt+1<=p.query(num+1,n):
s.append("(")
f(num+1,cnt+1)
s.pop()
if cnt>0 and T[i][num]!="(":
s.append(")")
f(num+1,cnt-1)
s.pop()
f(0,0)
right = list(set(right))
dic = collections.defaultdict(int)
for i in range(len(right)):
dic[right[i]]=i
bm=BipartiteMatching(n,len(right))
for i in range(n):
for j in li[i]:
bm.add_edge(i,dic[j])
if bm.max_matching()!=n:
print(-1)
exit()
li2=bm.get_matching()
li2.sort()
for i,j in li2:
print(right[j])