【競プロ典型90問】006の解説（python）

概要

競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。

※順次、全ての問題の解説記事を挙げていく予定です。
※★6以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）

問題006-Smallest Subsequence

問題

英小文字のみからなる、長さ N の文字列 S が与えられます。
長さが K である S の部分列のうち、辞書順で最小であるものを出力してください。

解き方

まず初めに、部分列を全列挙してから辞書順最小を得る方法が考えられますが、この考えではn文字からk文字を選んだ時の取り出し方 $nCk$ の全列挙になるため、k = 1, n 以外の時は、$O(N^2)$以上となりTLEになってしまいます。

ここで辞書順というのは、先頭の文字から順に順番が決まっていくため、先頭の文字が決まっているときにその後の文字はどうでも良いことが分かります。
（1文字が"a"の文字列Aと"b"の文字列BがあったらAの２文字目以降が全部"z"だろうが関係ない。）
そのため、この問題は前側から貪欲に辞書順最小の文字を採用していけば良い問題ということが分かりました。

実装の流れとしては、
1. アルファベットの出現箇所をメモする
2. aから順番に出現箇所と残りの文字数が妥当か※を確認し、問題なければ採用する。また、i回目で採用した文字の出現箇所 < i+1回目の出現箇所にならなければいけないため、その確認に今回は二分探索を用いた。
※例えば、"bbbbab"という文字列から３文字選択するときに、aを先頭にすることは出来ないため。
3. 2をK文字になるまで繰り返す

引用元：競プロ典型90問 Github

実装

answer.py

import string
import bisect

# 入力の受け取り
N, K = map(int, input().split())
S = input()

# アルファベットのリスト
alphs = list(string.ascii_lowercase)

# アルファベットの位置をs_idxに格納
s_idx = {}

for a in alphs:
  s_idx[a] = []

for i in range(len(S)):
  s_idx[S[i]].append(i)

# 答えとなる文字列をans, 出現箇所をメモするmemoを定義
ans = ""
memo = 0
while K > 0:
  for a in alphs:
    # アルファベットの存在の確認
    if len(s_idx[a]) == 0:
      continue
    # 二分探索でmemoより後に出現箇所を探索
    j = bisect.bisect_left(s_idx[a], memo)
    # jが範囲外の場合、除外
    if j >= len(s_idx[a]):
      continue
    # 出現箇所と残りの文字数の確認
    if K + s_idx[a][j] <= N:
      memo = s_idx[a][j]+1
      ans += a
      K -= 1
      break

print(ans)

最後に

問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）

ここまでお読みいただきありがとうございました。