結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
ユーザー LyricalMaestro
提出日時 2025-10-04 18:58:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,095 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 82,684 KB
実行使用メモリ 96,232 KB
最終ジャッジ日時 2025-10-04 18:58:17
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

# https://yukicoder.me/problems/no/3291

from collections import deque

MAX_VALUE = float("inf")

def main():
    N, K = map(int ,input().split())
    T = input()

    words = {str(i):(chr(i - 1+ ord("a"))) for i in range(1, 26 + 1)}

    dp = [0] * (N + 1)
    dp[N] = 1
    for i in reversed(range(N)):
        for j in range(2):
            if i + j + 1<= N:
                t = T[i:(i + j + 1)]
                if t in words:
                    if dp[i] + dp[i + j + 1] <= 2 * K:
                        dp[i] += dp[i + j + 1]
                    else:
                        dp[i] = MAX_VALUE

    answer = []
    index = 0
    while index < N:
        for j in range(2):
            if index + j + 1 <= N:
                a = T[index:(index + j + 1)]
                if a in words:
                    if dp[index + 1 + j] >= K:
                        answer.append(words[a])
                        index += 1 + j
                        break
                    else:
                        K -= dp[index + 1 + j]
    print("".join(answer))




if __name__ == "__main__":
    main()
0