問題
https://atcoder.jp/contests/arc097/tasks/arc097_a
方針
- 解になりうる全ての文字列をリスト化する
- 重複してカウントしないように、集合を計算した後、リスト化する
- 辞書順にソートする
- Pythonでは文字列のリストに対して、ソートを行うと辞書順にソートが行われる
- 先頭からK番目の要素を取得する
ポイント
- 解の文字数は最大でKであることを利用して計算量を削減する
- なぜ、最大でKであることが保証できるかというと、例えば、文字数が4文字の文字列
hogeよりも、その接頭辞h, ho, hogは辞書順で必ず前にくる。そのためhogeが辞書順で4未満となることはありえない。つまり、辞書順でK番目に小さいものとして、文字数がK文字より大きい文字列を考慮する必要はない。コード
1
2
3
4
5
6
7
8s = input()
K = int(input())
st = set() # 集合
for i in range(K):
for j in range(len(s)-i):
st.add(s[j:j+i+1]) # 文字数がi+1となるように文字列をスライスし、集合に追加する
ls = list(st) # 集合のリスト化
print (sorted(ls)[K-1]) # ソートしてK番目の要素を取得
- なぜ、最大でKであることが保証できるかというと、例えば、文字数が4文字の文字列