ICPCアジア地区横浜大会2018 D問題 : Shortest Common Non-Subsequence

問題. Shortest Common Non-Subsequence

'0' と '1' からなる2つの文字列 が与えられる． と のどちらの部分文字列でもない '0' と '1' からなる文字列で最小の長さのものを求めよ．ただし，答えが複数ある場合は辞書順で最小のものを求めよ．

制約：

解法. 動的計画法

の場合で，下のような列挙木を考える．


根からオレンジ色の頂点までの経路で，訪れた順番に文字を並べると， と のどちらの部分文字列でもないものが得られる．ただし，根は空白文字で，頂点の側に書かれている数字は「 の 文字目 / の 文字目」を表している．この数字の組 を状態として，値をその頂点までの最短路長として動的計画法を行う．状態遷移として， の 文字目と の 文字目にいるときに，最も近い '0' と '1' への2通りが考えられるので，全体で 時間で計算可能である．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

void SetNext(const string &s, vector<vector<int>> &nxt) {
    const int n = s.size();
    int idx_0 = n + 1, idx_1 = n + 1;
    for (int i = n; 0 < i; --i) {
        nxt[i][0] = idx_0;
        nxt[i][1] = idx_1;
        if (s[i - 1] == '0') idx_0 = i;
        else idx_1 = i;
    }
    nxt[0][0] = idx_0; nxt[0][1] = idx_1;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    string p, q;
    cin >> p >> q;

    const int n_p = p.size(), n_q = q.size();
    vector<vector<int>> nxt_p(n_p + 2, vector<int>(2, n_p + 1));
    vector<vector<int>> nxt_q(n_q + 2, vector<int>(2, n_q + 1));

    SetNext(p, nxt_p);
    SetNext(q, nxt_q);

    const int INF = 2 * max(n_p, n_q);
    vector<vector<int>> dp(n_p + 2, vector<int>(n_q + 2, INF));
    dp[n_p + 1][n_q + 1] = 0;
    for (int i = n_p + 1; 0 <= i; --i)
        for (int j = n_q + 1; 0 <= j; --j)
            for (int k = 0; k < 2; ++k)
                if (dp[nxt_p[i][k]][nxt_q[j][k]] < INF)
                    dp[i][j] = min(dp[i][j], dp[nxt_p[i][k]][nxt_q[j][k]] + 1);

    string res;
    for (int i = 0, j = 0; i <= n_p || j <= n_q; ) {
        for (int k = 0; k < 2; ++k) {
            if (dp[i][j] == dp[nxt_p[i][k]][nxt_q[j][k]] + 1) {
                i = nxt_p[i][k];
                j = nxt_q[j][k];
                res += (char)('0' + k);
                break;
            }
        }
    }

    cout << res << endl;

    return 0;
}

まとめ

状態遷移や解の構成を実装するのが難しかった．
動的計画法の説明を書くと長くなるので絵でごまかした．