Codeforces Round #683 (Div. 1) B. Catching Cheaters (R1800)

結構悩んだ！！！

• 問題へのリンク

問題概要

長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、

• 

とする。 の考えられる最大値を求めよ。

制約

• 

考えたこと

単純にそれぞれの部分文字列を探索したのでは の計算量となってしまう。

ここで、LCS を求めるときの DP を思い出しながら、スコアを少し言い換えてみることにする。

• として 1 文字を付け加えたとき、スコアは 1 減少する
• として 1 文字を付け加えたとき、スコアは 1 減少する
• から 1 文字、 から 1 文字付け加えたとき、それらが等しいならば、スコアは 2 増加する

このことを踏まえれば、LCS を求める DP を少し改変するだけで、この問題も解くことができる。計算量は 。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, M;
    string S, T;
    cin >> N >> M >> S >> T;
    vector<vector<long long>> dp(N+1, vector<long long>(M+1, 0));
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            // まだ一つもマッチ開始してない場合
            if (dp[i][j] == 0) {
                if (i < N && j < M && S[i] == T[j]) chmax(dp[i+1][j+1], dp[i][j] + 2);
            }
            // すでにマッチ開始している場合
            else {
                if (i+1 <= N) chmax(dp[i+1][j], dp[i][j] - 1);
                if (j+1 <= M) chmax(dp[i][j+1], dp[i][j] - 1);
                if (i < N && j < M && S[i] == T[j]) chmax(dp[i+1][j+1], dp[i][j] + 2);
            }
        }
    }
    long long res = 0;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            chmax(res, dp[i][j]);
        }
    }
    cout << res << endl;
}