2002-02-01

競プロ典型 90 問 006 - Smallest Subsequence（★5）

AtCoder 競プロ典型90問競プロ典型90問とその類題競プロ典型90問難易度5 「次の要素」へのポインタを求める Greedy 辞書順文字列部分列テク:26文字のアルファベット文字を個別に考える前処理そのまま覚えたい典型問題 Greedy:辞書順最小を求める

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

問題概要

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

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

制約

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

辞書順最小 → 貪欲法！

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

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

もし先頭の文字が a であって、長さの部分文字列が存在するならば、先頭の文字は 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 と初期化しておく)

各に対して
- 文字 a, b, ... の順に見て行って、次の条件を満たす最小のを求める
  - S[k] がその文字である
  - $k \ge j$ である
  - S[k:] は $K - 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)