提出 #32641757

ソースコード 拡げる

def main(N, K, S):
    '''想定コード(下記URL)参照
    https://github.com/E869120/kyopro_educational_90/blob/main/sol/006.cpp
    '''
    # 前処理
    nex = [[N]*26]
    for i in range(N-1, -1, -1):
        a = nex[-1].copy()
        a[ord(S[i])-ord("a")] = i
        nex.append(a)
    nex = nex[::-1]
    
    # 一文字ずつ貪欲に決める
    ans = []
    curr_pos = 0
    for i in range(K):
        for j in range(26):
            nex_pos = nex[curr_pos][j]
            
            if N - nex_pos >= K-i:
                ans.append(j)
                curr_pos = nex_pos + 1
                break
                
    return "".join([chr(ord("a")+c) for c in ans])

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

print(main(N, K, S))

提出情報

提出日時
問題 006 - Smallest Subsequence（★5）
ユーザ arakaki_tokyo
言語 PyPy3 (7.3.0)
得点 5
コード長 784 Byte
結果 AC
実行時間 120 ms
メモリ 111556 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 5 / 5
結果
AC × 2
AC × 29
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 10_random_small_00.txt, 10_random_small_01.txt, 11_random_medium_00.txt, 11_random_medium_01.txt, 12_random_large_00.txt, 12_random_large_01.txt, 13_random_max_00.txt, 13_random_max_01.txt, 13_random_max_02.txt, 20_unique_small_00.txt, 20_unique_small_01.txt, 21_unique_medium_00.txt, 21_unique_medium_01.txt, 22_unique_large_00.txt, 22_unique_large_01.txt, 23_unique_max_00.txt, 23_unique_max_01.txt, 23_unique_max_02.txt, 30_equal_small_00.txt, 30_equal_small_01.txt, 31_equal_medium_00.txt, 31_equal_medium_01.txt, 32_equal_large_00.txt, 32_equal_large_01.txt, 33_equal_max_00.txt, 33_equal_max_01.txt, 33_equal_max_02.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 62 ms 61704 KiB
00_sample_01.txt AC 49 ms 61976 KiB
10_random_small_00.txt AC 46 ms 62004 KiB
10_random_small_01.txt AC 45 ms 62208 KiB
11_random_medium_00.txt AC 69 ms 78264 KiB
11_random_medium_01.txt AC 69 ms 78332 KiB
12_random_large_00.txt AC 101 ms 106660 KiB
12_random_large_01.txt AC 98 ms 102720 KiB
13_random_max_00.txt AC 107 ms 110872 KiB
13_random_max_01.txt AC 110 ms 110224 KiB
13_random_max_02.txt AC 90 ms 103196 KiB
20_unique_small_00.txt AC 53 ms 64688 KiB
20_unique_small_01.txt AC 49 ms 61792 KiB
21_unique_medium_00.txt AC 79 ms 82164 KiB
21_unique_medium_01.txt AC 63 ms 77588 KiB
22_unique_large_00.txt AC 87 ms 94460 KiB
22_unique_large_01.txt AC 107 ms 110360 KiB
23_unique_max_00.txt AC 108 ms 111548 KiB
23_unique_max_01.txt AC 108 ms 109680 KiB
23_unique_max_02.txt AC 106 ms 108776 KiB
30_equal_small_00.txt AC 52 ms 63672 KiB
30_equal_small_01.txt AC 53 ms 65256 KiB
31_equal_medium_00.txt AC 78 ms 86756 KiB
31_equal_medium_01.txt AC 71 ms 77836 KiB
32_equal_large_00.txt AC 99 ms 105616 KiB
32_equal_large_01.txt AC 120 ms 110196 KiB
33_equal_max_00.txt AC 109 ms 111504 KiB
33_equal_max_01.txt AC 109 ms 111544 KiB
33_equal_max_02.txt AC 111 ms 111556 KiB