けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

辞書順最小なものを求めるとき、しばしば貪欲法が有効ですね!

問題概要

英小文字のみからなる長さ  N の文字列  S が与えられます。

 S の長さ  K の部分文字列であって、辞書順最小のものを求めてください。

制約

  •  1 \le K \le N \le 10^{5}

辞書順最小 → 貪欲法!

「辞書順最小のものを求めよ」と言われたら、とにかく貪欲法!!!

まずは求めたい文字列の先頭の文字について、次のように考えます。


  • もし先頭の文字が a であって、長さ  K の部分文字列が存在するならば、先頭の文字は a であると考えてよい
    • 文字列  S にそもそも文字 a がないとダメ
    • 文字 a があったとしても、その後ろの文字数が  K-1 文字未満の場合はダメ
  • そのような部分文字列が存在しないならば、先頭の文字を b にできるかを考える
  • それもダメならば、先頭の文字を c にできるかを考える
  • それもダメならば、先頭の文字を d にできるかを考える
  • ...

2 文字目以降の都合など、お構いなしで OK!!!!!

とにかく 2 文字目以降が全部 z になったとしても、1 文字目が小さい方が勝ちです!!!

たとえば  S = "bbbbazzzz" で  K = 5 のとき、答えは "azzzz" です。

ちなみに、同じ文字が複数個あるならば、より先頭側にある文字を選ぶようにします。たとえば  S = "zzzazzzazzz" で  K = 5 のとき、答えは "aazzz" です。先頭の a を選ぶとき、 2 個あるうちの前の方の a を選びます。

具体的なアルゴリズム

以上の着想を具体的にアルゴリズムとしてまとめると、次のようになります。


文字列  S の中で、最後にとった文字の添字を  j とする (j = -1 と初期化しておく)

  •  i = 0, 1, \dots, K-1 に対して
    • 文字 a, b, ... の順に見て行って、次の条件を満たす最小の  k を求める
      • S[k] がその文字である
      •  k \ge j である
      • S[k:] N - i 文字以上ある
    • そのような  k が存在するならば、答えに S[k] を加える、存在しなければ次の文字を見る

計算量を見積もってみましょう。 k を探索する部分には  O(N) の計算量を要することから、 M をアルファベットの種類数として  O(MNK) となります。

このままでは間に合いません。

前処理

前処理として、次の配列 nex を求めましょう。この配列は極めて汎用性が高いので、実にさまざまな問題で活用できます!!!

いっそライブラリ化しても良いように思います。

github.com


nex[i][c] ← 文字列  S i 文字目以降で、文字  c が出現する最小の添字 (存在しない場合は  N)


たとえば、 S = "abca" のとき

  • nex[0][a] = 0
  • nex[0][b] = 1
  • nex[0][c] = 2
  • nex[0][d] = -1
  • nex[1][a] = 3
  • nex[1][b] = 1
  • nex[1][c] = 2
  • nex[2][a] = 3
  • nex[2][b] = -1
  • nex[2][c] = 2
  • nex[3][a] = 3
  • nex[3][b] = -1
  • nex[3][c] = -1

というようになります。

この配列は、文字列  S の後ろから眺めていくことにより、次のコードのように  O(MS) の計算量で求められます。

またこの配列 nex を使うと、先ほどの貪欲法において  k を探索する部分の計算量は  O(1) にできますので、全体の計算量は  O(MS) へと改善されます。

コード (C++ と Python3)

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// res[i][c] := i 文字目以降で最初に文字 c が登場する index
// 存在しないときは N
vector<vector<int> > calc_next(const string &S) {
    // 文字列 S の長さ
    int N = (int)S.size();

    // 答え
    vector<vector<int> > res(N + 1, vector<int>(26, N));

    // 後ろから見る
    for (int i = N - 1; i >= 0; --i) {
        // i + 1 文字目以降の結果を一旦 i 文字にコピー
        res[i] = res[i + 1];

        // i 文字目の情報を反映させる
        res[i][S[i] - 'a'] = i;
    }
    return res;
}

int main() {
    // 入力
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    // 前処理
    string res = "";
    auto nex = calc_next(S);

    // 貪欲法
    int j = -1;
    for (int i = 0; i < K; ++i) {
        for (char c = 'a'; c <= 'z'; ++c) {
            int k = nex[j + 1][c - 'a'];

            // ちゃんと K 文字が作れれば OK
            if (N - k >= K - i) {
                res += c;
                j = k;
                break;
            }
        }
    }
    cout << res << endl;
}

Python3

# res[i][c] := i 文字目以降で最初に文字 c が登場する index
# 存在しないときは N
def calc_next(S):
    # 文字列 S の長さ
    N = len(S)

    # 答え
    res = [[N] * 26 for _ in range(N + 1)]

    # 後ろから見る
    for i in range(N - 1, -1, -1):
        # i + 1 文字目以降の結果を一旦 i 文字にコピー
        for j in range(26):
            res[i][j] = res[i + 1][j]

        # i 文字目の情報を反映させる
        res[i][ord(S[i]) - ord('a')] = i

    # 答えを返す
    return res

# 入力
N, K = map(int, input().split())
S = input()

# 前処理
res = ''
nex = calc_next(S)

# 貪欲法
j = -1
for i in range(K):
    for ordc in range(26):
        k = nex[j + 1][ordc]

        # ちゃんと K 文字が作れれば OK
        if N - k >= K - i:
            res += chr(ord('a') + ordc)
            j = k
            break
print(res)