E - Don’t Be a Subsequence
問題
英小文字のみからなる文字列で、文字列 S の部分列でないようなもののうち最短のものを求めよ。
複数ある場合は、その中で辞書順最小のものを求めよ。
制約
- 1≤∣S∣≤2⋅105
考察
以降、文字列 S に対する解を f(S) とする。
S が空文字列でもよいことに注意(この場合、解は a となる)。
まずは ∣f(S)∣ を求める。これは f(S) の先頭の文字 c で場合分けすると求められる。
- S 中に c が現れない場合。 c 自体が条件を満たすので長さは 1 となる。
- 現れる場合。 S 中で現れる c のうち一番前のものを Si とすると、最適解は c+f(S[i+1,∣S∣)) となる。
ここで S[i,∣S∣) は S の i 文字目以降からなる文字列を表す。
よって全ての 0≤i≤∣S∣ について以下を求めればよい。
- 各文字 c について、 S[i,∣S∣) 中で現れる c のうち一番手前のものの index。
- ∣f(S[i,∣S∣))∣
これは i について降順に求めていくことで、全体で Θ(σ∣S∣) で求められる (σ は文字種数)。
上のアルゴリズムを使うと、「先頭が c であり、条件を満たすような文字列の長さの最小値」が求められる。これが最小となるような c のうち辞書順最小のものを先頭にすれば、 f(S) の復元ができる。
実装例
c が含まれない場合の処理を場合分けなしでやろうとしたら、却って実装がバグった。
自然に解釈できない番兵は使うべきではない。
提出 #18405139 - AtCoder Regular Contest 081
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <iostream>
#include <vector>
#include <string>
template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
using namespace std;
void solve() {
string s;
cin >> s;
int n = s.length();
vector<int> len(n + 1, n); // S[i, n)に対する解の長さ
len[n] = 1;
auto nxt = vec(n + 1, vec(26, -1));
// S[i, n)で一番手前にあるcの位置(なければ-1)
for (int i = n - 1; i >= 0; --i) {
nxt[i] = nxt[i + 1];
nxt[i][s[i] - 'a'] = i;
for (auto j : nxt[i]) {
int nlen = (j == -1 ? 0 : len[j + 1]) + 1;
len[i] = min(len[i], nlen);
}
}
int i = 0, l = len[0];
while (l > 0) {
int nc = -1; // 次の文字
for (int c = 0; c < 26; ++c) {
auto j = nxt[i][c];
int nlen = (j == -1 ? 0 : len[j + 1]) + 1;
if (nlen == l) {
nc = c;
break;
}
}
cout << char(nc + 'a');
i = nxt[i][nc] + 1;
--l;
}
cout << "\n";
}
|