結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
ユーザー titia
提出日時 2025-10-08 04:41:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,075 bytes
コンパイル時間 650 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 114,952 KB
最終ジャッジ日時 2025-10-08 04:41:47
合計ジャッジ時間 6,415 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 2 RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

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

if K==1:
    ANS=[]
    for i in range(N):
        ANS.append(chr(int(S[i])+96))
    print("".join(ANS))
    exit()

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


ind=0
ANS=[]

while ind<len(X):
    #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