#1182178 (PyPy3) No.3738 Right Hamiltonian

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 04:50:12
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 393 ms / 2,000 ms
• コード長: 4,633 bytes
• コンパイル時間: 80 ms
• コンパイル使用メモリ: 83,840 KB
• 実行使用メモリ: 139,368 KB
• 最終ジャッジ日時: 2026-09-19 13:03:09
• 合計ジャッジ時間: 8,242 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_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')