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

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

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

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

問題へのリンク

問題概要

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

制約

  •  1 \le |S|, |T| \le 4000

考えたこと

これは完全に「部分文字列を走査する 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;
}