fork(8) download
  1. A,B=gets,gets.split
  2. L=[]
  3. R=[]
  4. U=[]
  5. D=[]
  6. N=[]
  7. C=[]
  8. S=[]
  9. O=[0]*81
  10. z='A'
  11. (0..324).map{|j|U<<j;D<<j;R<<(j+1)%325;L<<(j+324)%325;N<<j;C<<j;S<<0}
  12. X=->s,j,c,cf,n{
  13. j<81 ? (z==A[j]?(0..8).map{|i|X[s-1-i,j+1,c+[i],cf+[1+j,1+81+27*i+j/9,1+81+27*i+9+j%9,1+81+27*i+18+j/3%3+j/27*3],n+[i+1]]}:X[s,j+1,c,cf,n+[0]]if s>=0)
  14. : (h=U.size;cf.uniq.sort.map{|l|N<<n;L<<(L[h]||h);R<<h;U<<U[l];D<<l;C<<l;S[l]+=1;L[R[-1]]=R[L[-1]]=U[D[-1]]=D[U[-1]]=L.size-1}if s==0)
  15. }
  16. Y=->c{L[R[c]]=L[c];R[L[c]]=R[c];i=D[c];(j=R[i];(U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]-=1;j=R[j])while j!=i;i=D[i])while i!=c}
  17. Z=->c{i=U[c];(j=L[i];(S[C[j]]+=1;U[D[j]]=j;D[U[j]]=j;j=L[j])while j!=i;i=U[i])while i!=c;L[R[c]]=c;R[L[c]]=c}
  18. B.map{|k|X[k.to_i,0,[],[],[]];z=z=='Z'?'a':z.next}
  19. s=->k{
  20. c=R[0]
  21. c<1 ? ($><<(O[0,k].map{|s|N[s]}.transpose.map &:max)*"")
  22. : (g=S[b=c];g=S[b=c]if S[c]<g while 0<c=R[c];Y[b];r=D[b];(O[k]=r;j=R[r];(Y[C[j]];j=R[j])while j!=r;s[k+1];r=O[k];c=C[r];j=L[r];(Z[C[j]];j=L[j])while j!=r;r=D[r])while r!=b;Z[b])
  23. }
  24. s[0]
  25.  
  26.  
Success #stdin #stdout 2.79s 10864KB
stdin
AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17
stdout
215647398368952174794381652586274931142593867973816425821739546659428713437165289