自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型90問:006 - Smallest Subsequence(★5)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_f

挑戦結果

  • 結果:できなかった
  • 時間:30分ぐらい

考えたこと

  • 全列挙を再帰的に作ることはできると思ったけど、計算量的にどう考えても無理だった。
  • 貪欲に求める方法も考えたけど、思いつかなかった。

解説を読んだふりかえり

  • 貪欲な方法を思いつかなかったし、その上、事前計算が必要だったようで無理だった。
  • なんかもう一度解いても解ける気がしてないけど、辞書式最小は前から貪欲法は覚えておこう

公式解説

https://twitter.com/e869120/status/1379202843622576130?s=20

ソース

from string import ascii_lowercase
N,K = [int(x) for x in input().split()]
S = input()
INF = float('inf')

# 事前の計算用のテーブル
C = [[INF] * N for _ in range(len(ascii_lowercase))]
L = [INF] * len(ascii_lowercase)
# 後ろから、文字がある場所を計算
for i,ch in reversed(list(enumerate(S))):
    L[ord(ch)-ord('a')] = i
    for a in ascii_lowercase:
        aidx = ord(a)-ord('a')
        C[aidx][i] = L[aidx]

ans = ""
idx = 0
# Sのidx文字目を候補にするかどうか
# 一番若い文字をピックアップできるかどうかは、ピックアップした後続に文字数があればOK
while (idx < N and len(ans)<K):
    for j,ch in enumerate(ascii_lowercase):
        if N-C[j][idx] >= K-len(ans):
            ans += ch
            idx = C[j][idx]
            # print(ans)
            break
    idx+=1

print(ans)