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

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

AtCoder ARC 081 E - Don't Be a Subsequence (黄色, 600 点)

部分列 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;
}