結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
ユーザー titia
提出日時 2025-10-08 04:44:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 2,094 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 117,324 KB
最終ジャッジ日時 2025-10-08 04:44:14
合計ジャッジ時間 5,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,K=map(int,input().split())
S=input().strip()

X=[]
ind=0
while ind<N:
    if ind+1<N and S[ind+1]=="0":
        if S[ind]=="1":
            X.append("j")
        else:
            X.append("t")
        ind+=2
    else:
        X.append(S[ind])
        ind+=1

DP=[-1]*(len(X)+10)
DP2=[-1]*(len(X)+10)

    
# X[x:]では何通り？
def calc(x):
    if DP[x]!=-1:
        return DP[x]
    
    if x>=len(X)-1:
        DP[x]=1
        return 1

    a=X[x]+X[x+1]

    if "j" in a or "t" in a:
        ANS=calc(x+1)
        DP[x]=ANS
        return ANS

    if 11<=int(a)<=19 or 21<=int(a)<=26:
        ANS=calc(x+2)*2+calc2(x+1)
        DP[x]=min(10**18+5,ANS)
        return DP[x]
    else:
        ANS=calc(x+1)
        DP[x]=ANS
        return ANS
    
# x,x+1を変化させたとき、何通り？
def calc2(x):
    if DP2[x]!=-1:
        return DP2[x]
    
    if x>=len(X)-1:
        DP2[x]=0
        return 0

    a=X[x]+X[x+1]

    if "j" in a or "t" in a:
        DP2[x]=0
        return 0

    if 11<=int(a)<=19 or 21<=int(a)<=26:
        ANS=calc(x+2)
        DP2[x]=min(10**18+5,ANS)
        return DP2[x]
    else:
        DP2[x]=0
        return 0

for i in range(len(X)-1,-1,-1):
    calc(i)

ind=0
ANS=[]

while ind<len(X):
    if K>1:
        #print(ind,ANS,K)
        OK=ind
        NG=len(X)-1

        while NG>OK+1:
            #print(OK,NG,calc(OK),calc(NG))
            mid=(OK+NG)//2

            score=calc(mid)

            if score>=K:
                OK=mid
            else:
                NG=mid

        #print(OK)

        K-=calc(OK+1)
        for i in range(ind,OK):
            if X[i]=="j" or X[i]=="t":
                ANS.append(X[i])
            else:
                ANS.append(chr(int(X[i])+96))

        ANS.append(chr(int(X[OK]+X[OK+1])+96))
        ind=OK+2

    if K==1:
        for i in range(ind,len(X)):
            if X[i]=="j" or X[i]=="t":
                ANS.append(X[i])
            else:
                ANS.append(chr(int(X[i])+96))
        break

print("".join(ANS))
0