競プロ典型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)