def C():
from copy import deepcopy
from itertools import product
HA, WA = map(int, input().split())
A = [input() for _ in range(HA)]
HB, WB = map(int, input().split())
B = [input() for _ in range(HB)]
HX, WX = map(int, input().split())
X = [input() for _ in range(HX)]
def normalize(m):
ret = []
left_top = None
for i in range(len(m)):
for j in range(len(m[0])):
if m[i][j] == "#":
if left_top:
ret.append(tuple(a - b for a, b in zip([i, j], left_top)))
else:
left_top = (i, j)
ret.append((0, 0))
return ret
x_pat = normalize(X)
m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)]
for i, j in product(range(HA), range(WA)):
if A[i][j] == "#":
m_base[HB + 8 + i][WB + 8 + j] = "#"
for i in range(HB + HA + 16):
for j in range(WB + WA + 16):
m = deepcopy(m_base)
for k in range(HB):
for l in range(WB):
if B[k][l] == "#":
m[i + k][j + l] = "#"
if x_pat == normalize(m):
print("Yes")
return
print("No")test_all(C)
...
for i in range(HB + HA + 17):
for j in range(WB + WA + 17):
...
def C():
from copy import deepcopy
from itertools import product
HA, WA = map(int, input().split())
A = [input() for _ in range(HA)]
HB, WB = map(int, input().split())
B = [input() for _ in range(HB)]
HX, WX = map(int, input().split())
X = [input() for _ in range(HX)]
def normalize(m):
ret = []
left_top = None
for i in range(len(m)):
for j in range(len(m[0])):
if m[i][j] == "#":
if left_top:
ret.append(tuple(a - b for a, b in zip([i, j], left_top)))
else:
left_top = (i, j)
ret.append((0, 0))
return ret
x_pat = normalize(X)
m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)]
for i, j in product(range(HA), range(WA)):
if A[i][j] == "#":
m_base[HB + 8 + i][WB + 8 + j] = "#"
for i in range(HB + HA + 17):
for j in range(WB + WA + 17):
m = deepcopy(m_base)
for k in range(HB):
for l in range(WB):
if B[k][l] == "#":
m[i + k][j + l] = "#"
if x_pat == normalize(m):
print("Yes")
return
print("No")test_all(C)
判定にnormalizeを用いる発想は別解 by evimaと一緒だけど、その前にconvertして探索を容易にしたり、全体の実装が段違いに洗練されている…
結局私の実装力不足でした。本当にありがとうございました。
参考というか目標としてevimaさんの別解を以下に引用します。キレイだよなぁ～
def C_editorial():
''' editorial by evima
https://atcoder.jp/contests/abc307/editorial/6650
'''
def convert(H, W, S):
s = set()
for i in range(H):
for j in range(W):
if S[i][j] == '#':
s.add((i, j))
return s
def normalize(s):
my = min(y for (y, x) in s)
mx = min(x for (y, x) in s)
return set((y - my, x - mx) for (y, x) in s)
HA, WA = map(int, input().split())
A = normalize(convert(HA, WA, [input() for _ in range(HA)]))
HB, WB = map(int, input().split())
B = normalize(convert(HB, WB, [input() for _ in range(HB)]))
HX, WX = map(int, input().split())
X = normalize(convert(HX, WX, [input() for _ in range(HX)]))
ans = False
for dy in range(-HX, HX):
for dx in range(-WX, WX):
ans |= normalize(A.union((y + dy, x + dx) for (y, x) in B)) == X
print('Yes' if ans else 'No')test_all(C_editorial)
def D():
N = int(input())
S = input()
A = [0] * N
start = []
for i, c in enumerate(S):
if c == "(":
start.append(i)
elif c == ")" and start:
A[start.pop()] = 1
A[i] = -1
flag = 0
ans = []
for c, a in zip(S, A):
flag += a
if flag == 0 and a != -1:
ans.append(c)
print(*ans, sep="")test_all(D)
AtCoder Inc.
