Submission #5421609

---

Source Code Expand

s = input()
k = int(input())
alph = "abcdefghijklmnopqrstuvwxyz"

#典型？：辞書順最小な解の復元は後ろからDP行う
#dp[i][c] := i文字目より後ろ(i,len(s)]のsについて文字cから始まる部分文字列の通り数
dp = [[0]*len(alph) for _ in range (len(s)+1)]

#DPテーブル作成
for i in range(len(s))[::-1]:
    for ic in range(len(alph)):
        if s[i] != alph[ic]:
            dp[i][ic] = dp[i+1][ic]
        else:
            dp[i][ic] = sum(dp[i+1]) + 1
        
#Eelになる場合（ところでEelって何？）
if sum(dp[0])<k:
    print("Eel")
    exit()

#復元
i = 0
ans = ""   
while i < len(s):
    for ic in range(len(alph)):
        if dp[i][ic] < k:
            k = k - dp[i][ic]
        elif dp[i][ic] >= k:
            ans += alph[ic]
            k-=1
            while s[i] != alph[ic]:
                i += 1
            i += 1
            break
    if k <= 0:
        print(ans)
        exit()

Submission Info

Judge Result