CODE FESTIVAL 2015 あさプロ Middle B - ヘイホー君と削除

問題

code-festival-2015-morning-middle.contest.atcoder.jp

解法

文字列を2つに分断して最長共通部分文字列(LCS:Longest Common Substring)を求めると操作回数も分かる。

入力例1の場合なら
"","abacbabc" -> ""
"a","bacbabc" -> "a"
"ab","acbabc" -> "ab"
"aba","cbabc" -> "ba"
"abac","babc" -> "bac"
"abacb","abc" -> "abc"
"abacba","bc" -> "bc"
"abacbab","c" -> "c"
LCSを残してそれ以外を削除すれば平方を作ることができる。最長共通部分文字列を残しているのだから、これ以上長い文字列を残すことはできない。この例の場合は"bacbac"か"abcabc"を残すのが最適。

ちなみにLCSは動的計画法で求めることができる（蟻本参照）。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
 
int lcs(string s, string t) {
    int m = s.length();
    int n = t.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    rep (i, m) rep (j, n) {
        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[m][n];
}
 
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 1e9;
    rep (i, s.length()) {
        int l = lcs(s.substr(0, i), s.substr(i));
        chmin(ans, n - l * 2);
    }
    cout << ans << endl;
}

感想

ライブラリにLCS入れておくべきだった。