AOJ 1392 Shortest Common Non-Subsequence (ICPC アジア 2018 D) (500 点)

ARC 081 E - Don't Be a Subsequence の文字列が 2 個になったバージョン！

問題へのリンク

問題概要

2 つの '0' と '1' で構成された文字列 S, T が与えられる。
S の部分文字列でも T の部分文字列でもないような文字列のうち長さが最小のものを求めよ。複数ありうるときはそのうちの辞書順最小のものを求めよ。

制約

• 

考えたこと

これは完全に「部分文字列を走査する DP」の問題リストの新たな一ページとなる問題。

• 部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集

に書いた考え方を使う。この中の特に「問題 3： ARC 081 E - Don't Be a Subsequence」を自然に拡張すればいい。

• dp[ i ][ j ] := S の i 文字目以降と、T の j 文字目以降についての最小の長さ

としてあげて、基本的には

• dp[ i ][ j ] = min(dp[ nextS[ i ][ 0 ] + 1 ][ nextT[ j ][ 0 ] + 1 ] + 1, dp[nextS[ i ][ 1 ] + 1 ][ nextT[ j ][ 1 ] + 1 ] + 1)

という遷移をしてあげればいい。境界条件がややこしい。

• dp[ i ][ j ] = 1　(まだ 1 文字 '0' を追加すべき状況)
• dp[ i+1 ][ j+1 ] = 0　(もう完全にそれも終わってる状況)

というタイプの境界条件を採用した。なおちょっと境界付近の処理をいじってあげれば、基本的に同じ遷移式で「S の部分文字列でもあり T の部分文字列でもある」とはなっていないような最短の文字列 (のうち辞書順最小のもの) も求められる気がする。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
using pint = pair<int,int>;
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>(2, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 2; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'0'] = i;
    }
    return res;
}

int main() {
    string S, T; cin >> S >> T;
    auto nextS = calcNext(S), nextT = calcNext(T);
    int n = (int)S.size(), m = (int)T.size();
    
    vector<vector<int> > dp(n+2, vector<int>(m+2, 1<<29));
    vector<vector<pair<char,pint> > > recon(n+2, vector<pair<char,pint> >(m+2, {'0', pint(n,m)}));
    dp[n][m] = 1;
    dp[n+1][m+1] = 0;
    for (int i = n+1; i >= 0; --i) {
        for (int j = m+1; j >= 0; --j) {
            if (i == n+1 && j == m+1) continue;
            for (int k = 0; k < 2; ++k) {
                int ni, nj;
                if (i >= n) ni = n; else ni = nextS[i][k];
                if (j >= m) nj = m; else nj = nextT[j][k];
                if (chmin(dp[i][j], dp[ni+1][nj+1] + 1)) {
                    recon[i][j] = {'0'+k, pint(ni+1,nj+1)};
                }
            }
        }
    }
    string res = "";
    int i = 0, j = 0;
    for (int k = 0; k < dp[0][0]; ++k) {
        auto p = recon[i][j];
        res += p.first;
        i = p.second.first;
        j = p.second.second;
    }
    
    cout << res << endl;
}