JAG Practice Contest for ACM-ICPC Asia Regional 2015 A - M and A

問題

jag2015autumn.contest.atcoder.jp

解法

S からは交互に文字を取っていくことになるので, 要するに焦点となるのは, 「S から 1 つおきに文字を取っていったもの(s とする)と, T の部分文字列とで, 最長共通部分文字列が s に一致するかどうか」ということになります。s の候補は 2 つある(0-index で 0 番目から始まる文字か, 1 から始まる文字か)のに注意します。

これはよくある dp で調べられるので, O(N^2) ですね。

int calc(string s, string t) {
    int n = s.size(), m = t.size();
    vector<vector<int> > dp(n+1, vector<int>(m+1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j]+1;
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    return dp[n][m];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;
    string s1, s2;
    int N = S.size();
    for (int i = 0; i < N; i+=2) s1 += S[i];
    for (int i = 1; i < N; i+=2) s2 += S[i];
    if (calc(s1, T) == (int)s1.size() || calc(s2, T) == (int)s2.size()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}