部分列 DP の考え方を試せる問題
問題概要
文字列 A が与えられる。
A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。
複数考えられる場合にはそのうち辞書順最小のものを求めよ。
制約
- 1 <= |A| <= 2 × 105
- A は英小文字のみからなる
解法
部分文字列に関する問題には典型手法がある (これを参照)。それを応用する。今回は「辞書順最小な復元をする」という要求もあるので、そのような場合には
- 後ろから DP する
というこれまた典型対策がある。部分列 DP を応用して「後ろから DP」という形に対応して、以下のようにする。ここで
- next[ i ][ j ] := i 文字目以降で最初に 'a ' + j が登場する index
としている。
【DP 定義】
dp[ i ] := i 文字目以降について「部分文字列とならない」最短の文字列長
(通常の「部分文字列数え上げ DP」と異なり、必ずしも i 文字目自体を採用しなくてもよいことに注意)
【DP 遷移】
各 j に対して、dp[ i ] = min(dp[ i ], dp[ next[ i ][ j ] ] + 1)
(次の文字を 'a'〜'z' で場合分けしている)
【DP 初期化】
dp[ n ] = 1
#include <iostream> #include <string> #include <vector> using namespace std; // chmin template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n) vector<vector<int> > calcNext(const string &S) { int n = (int)S.size(); vector<vector<int> > res(n+1, vector<int>(26, n)); for (int i = n-1; i >= 0; --i) { for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j]; res[i][S[i]-'a'] = i; } return res; } int main() { string S; cin >> S; int n = (int)S.size(); // 前処理配列 auto next = calcNext(S); // DP vector<int> dp(n+1, 1<<29); // DP テーブル vector<pair<char, int> > recon(n+1, {'?', n}); // 復元用テーブル dp[n] = 1; for (int i = n - 1; i >= 0; --i) { for (int j = 0; j < 26; ++j) { // 次の文字がないとき if (next[i][j] == n) { if (dp[i] > 1) dp[i] = 1, recon[i] = {'a'+j, n}; } // 次の文字があるとき else if (chmin(dp[i], dp[next[i][j] + 1] + 1)) recon[i] = {'a'+j, next[i][j] + 1}; } } // 復元 string res = ""; int index = 0; while (index < n) { auto p = recon[index]; res += p.first; index = p.second; } cout << res << endl; }