結果
| 問題 | No.3738 Right Hamiltonian |
| コンテスト | |
| ユーザー |
👑  kencho
|
| 提出日時 | 2026-09-11 00:42:27 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 358 ms / 2,000 ms |
| + 643µs | |
| コード長 | 8,132 bytes |
| 記録 | |
| コンパイル時間 | 107 ms |
| コンパイル使用メモリ | 83,632 KB |
| 実行使用メモリ | 139,680 KB |
| 最終ジャッジ日時 | 2026-09-19 13:15:49 |
| 合計ジャッジ時間 | 7,816 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge5_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点 | 80 % | AC * 38 |
| 満点 | 20 % | AC * 60 |
| 合計 | 4 * 100% = 400 点 |
ソースコード
import sys
from array import array
input = sys.stdin.buffer.readline
def solve():
H0, W0 = map(int, input().split())
A = [input().strip() for _ in range(H0)]
R = [i for i, s in enumerate(A) if b"." in s]
ro, rb = R[0], R[-1]
co = min(s.find(b".") for s in A if b"." in s)
cb = max(s.rfind(b".") for s in A)
A = [s[co : cb + 1] for s in A[ro : rb + 1]]
H, W = len(A), len(A[0])
N = sum(s.count(b".") for s in A)
V = W + 2
D = (-V, 1, V, -1)
X = (-1, 0, 1, 0)
Y = (0, 1, 0, -1)
mp = {D[i]: i for i in range(4)}
ID = lambda x, y: (x + 1) * V + y + 1
G = b"#" * V + b"".join(b"#" + s + b"#" for s in A) + b"#" * V
def make(st, z):
q = []
for d, n in z:
if not n:
continue
if q and q[-1][0] == d:
q[-1][1] += n
else:
q.append([d, n])
s = ("F" * q[0][1] if q else "") + "".join(
"R" + "F" * (n - 1) for d, n in q[1:]
)
return st // V + ro, st % V + co, "URDL"[q[0][0] if q else 0], s
if H == 1:
return make(ID(0, 0), [(1, N - 1)]) if N == W else None
if W == 1:
return make(ID(0, 0), [(2, N - 1)]) if N == H else None
P = (
[ID(0, j) for j in range(W - 1)]
+ [ID(i, W - 1) for i in range(H - 1)]
+ [ID(H - 1, j) for j in range(W - 1, 0, -1)]
+ [ID(i, 0) for i in range(H - 1, 0, -1)]
)
L = len(P)
def seg(p):
z = []
for x, y in zip(p, p[1:]):
d = mp[y - x]
if z and z[-1][0] == d:
z[-1][1] += 1
else:
z.append([d, 1])
return z
on = [G[x] == 46 for x in P]
B = sum(on)
if B < L:
s = [i for i in range(L) if on[i] and not on[i - 1]]
if len(s) != 1:
return None
arc = []
i = s[0]
while on[i]:
arc.append(P[i])
i = (i + 1) % L
if len(arc) != B or len(arc) < 2:
return None
out = seg(arc)
fd, ld = out[0][0], out[-1][0]
used = bytearray(len(G))
def walk(p, d, t, k):
z = []
c = 0
while 1:
q = p + D[d]
if G[q] != 46 or used[q] == k:
d = (d + t) & 3
q = p + D[d]
if G[q] != 46 or used[q] == k:
return p, z, c
used[q] = k
p = q
c += 1
if z and z[-1][0] == d:
z[-1][1] += 1
else:
z.append([d, 1])
for o in range(2):
k = o + 1
for x in arc:
used[x] = k
if o:
_, b, v = walk(arc[-1], (ld + 1) & 3, 1, k)
e, a, u = walk(arc[0], (fd + 1) & 3, -1, k)
else:
e, a, u = walk(arc[0], (fd + 1) & 3, -1, k)
_, b, v = walk(arc[-1], (ld + 1) & 3, 1, k)
if B + u + v == N:
return make(e, [((d + 2) & 3, n) for d, n in a[::-1]] + out + b)
return None
C = list(map(bytes, zip(*A)))
ps = [array("I", [0]) * (W + 1)]
for s in A:
q = array("I", [0]) * (W + 1)
p = ps[-1]
v = 0
for j, x in enumerate(s, 1):
v += x == 46
q[j] = p[j] + v
ps.append(q)
def cnt(z):
u, d, l, r = z
return (
0
if u > d or l > r
else ps[d + 1][r + 1] - ps[u][r + 1] - ps[d + 1][l] + ps[u][l]
)
def ent(z, d, t):
u, b, l, r = z
return (
((b, l), (u, l), (u, r), (b, r))
if t == 1
else ((b, r), (b, l), (u, l), (u, r))
)[d]
ei = (0, 3, 1, 2)
ri = (2, 0, 3, 1)
li = (3, 1, 2, 0)
sg = (1, 1, -1, -1)
def shrink(z, x, y, d, t):
q = list(z)
c = x if d % 2 == 0 else y
q[ei[d]] = c
j = (ri if t == 1 else li)[d]
c = y if d % 2 == 0 else x
q[j] = c + (sg[d] if t == 1 else -sg[d])
return tuple(q)
def arm(z, st, d, t):
rem = cnt(z)
ev = []
ex, ey = divmod(st, V)
ex -= 1
ey -= 1
while rem:
u, b, l, r = z
h = b - u + 1
w = r - l + 1
lim = (min(h, w) - 1) // 2
if lim:
walls = h * w - rem
def full(k):
q = (u + k, b - k, l + k, r - k)
return (h - 2 * k) * (w - 2 * k) - cnt(q) == walls
if full(1):
lo, hi = 1, 2
while hi <= lim and full(hi):
lo, hi = hi, hi * 2
hi = min(hi, lim + 1)
while hi - lo > 1:
m = (lo + hi) // 2
if full(m):
lo = m
else:
hi = m
ev.append((*z, d, t, lo))
z = (u + lo, b - lo, l + lo, r - lo)
rem = cnt(z)
x, y = ent(z, d, t)
ex, ey = x - X[d], y - Y[d]
continue
x, y = ent(z, d, t)
if d == 0:
j = C[y].rfind(b"#", u, x + 1)
n = x - (j if j >= 0 else u - 1)
elif d == 1:
j = A[x].find(b"#", y, r + 1)
n = (j if j >= 0 else r + 1) - y
elif d == 2:
j = C[y].find(b"#", x, b + 1)
n = (j if j >= 0 else b + 1) - x
else:
j = A[x].rfind(b"#", l, y + 1)
n = y - (j if j >= 0 else l - 1)
if not n:
return None
ex = x + X[d] * (n - 1)
ey = y + Y[d] * (n - 1)
q = shrink(z, ex, ey, d, t)
nr = cnt(q)
if rem - nr != n:
return None
ev.append((d, n))
z, rem, d = q, nr, (d + t) & 3
return ex, ey, ev
def expand(a):
out = []
for e in a[2]:
if len(e) == 2:
out.append(e)
continue
u, b, l, r, d, t, k = e
z = (u, b, l, r)
for _ in range(k):
for _ in range(4):
x, y = ent(z, d, t)
u, b, l, r = z
n = (
x - u + 1
if d == 0
else r - y + 1
if d == 1
else b - x + 1
if d == 2
else y - l + 1
)
x += X[d] * (n - 1)
y += Y[d] * (n - 1)
out.append((d, n))
z = shrink(z, x, y, d, t)
d = (d + t) & 3
return out
for k in range(L):
A0, B0 = P[(k + 1) % L], P[k]
ar, ac = divmod(A0, V)
br, bc = divmod(B0, V)
ar -= 1
ac -= 1
br -= 1
bc -= 1
if ar == br:
x = max(ac, bc)
Q = (1, H - 2, 1, x - 1)
R = (1, H - 2, x, W - 2)
za, zb = (R, Q) if ac >= x else (Q, R)
else:
x = max(ar, br)
Q = (1, x - 1, 1, W - 2)
R = (x, H - 2, 1, W - 2)
za, zb = (R, Q) if ar >= x else (Q, R)
fd = mp[P[(k + 2) % L] - A0]
ld = mp[B0 - P[(k - 1) % L]]
a = arm(za, A0, (fd + 1) & 3, -1)
if a is None:
continue
b = arm(zb, B0, (ld + 1) & 3, 1)
if b is None:
continue
arc = [P[(k + 1 + j) % L] for j in range(L)]
return make(
ID(a[0], a[1]),
[((d + 2) & 3, n) for d, n in expand(a)[::-1]] + seg(arc) + expand(b),
)
ans = solve()
if ans is None:
print(-1)
else:
r, c, d, s = ans
sys.stdout.write(f"{r} {c} {d}\n{len(s)}\n{s}\n")