面白かった

問題概要

文字列 $S$ が与えられる。あらかじめ文字列の中の $K$ 文字を自由に変更することができる。

こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。

制約

$1 \le S \le 300$
$1 \le K \le |S|$

考えたこと

もし $K = 0$ だったら、

dp[ i ][ j ] := $S$ について左から i 文字分、右から j 文字分の中での LCS の長さ

という感じに解くことができそう。普通に LCS を求める DP と同様にして

chmax(dp[ i + 1 ][ j ], dp[ i ][ j ])
chmax(dp[ i ][ j + 1 ], dp[ i ][ j ])
もし S[ i ] == S[ j - 1 ] なら chmax(dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + 1)

という風にして DP 遷移をして、dp[ N ][ N ] を求めればよい。 $K$ 文字変更できるときはどうしたらよいか。難しいこととして、

abcabc

とかで、最初に左の a と右の c を見比べて、ここで操作を 1 回使って

cbcabc

とかにしたとすると、この「最初の文字を a から c にした」という変更が後々まで効いてくる可能性があるということ。すなわち、

左から進んでいく DP の index ポインタ
右から進んでいく DP の idnex ポインタ

とを考えたとき、左からについてはもう「c に変わった a」には触れることはないが、右からのポインタはやがてこの「c に変わった a」に触れることになる。このときに、この変更があることを記憶しておかないと、上手く更新できなくなってしまう。。。ように思える。この状態を打開したい。

文字列を 2 つに割ってそれぞれだけ考えれば良い

少し考えてみると、文字列 S を 2 つに割って

S = A + B

みたいに分割して (分割の仕方は探索する必要がある)、

A を左から
B を右から

同じ文字同士をペアにしてマッチングして行く感じの問題になることがわかる。また同じ文字でなくても $K$ 回までなら異なる文字同士をマッチングさせてよいととらえることができる。

そして、さきほどの DP で

左側から進むポインタが B に入ってから
右側から進むポインタが A に入ってから

というのは、単純に前半のペアを再び繰り返すのが最適であることがわかる。こうしてみると、操作が後先まで影響を及ぼさなくなっていることがわかる。

あとは注意点として、

S = A + B

だけでなく

S = A + 'x' + B ('x' は何かの文字)

という感じにした方がよいこともある。

(そもそも) 予め盤面や文字列を操作できるときの最適化

この問題に限らず、最短経路を求めたい盤面を変形したりもできるとき、一見考えるべきことが爆発的に増えて大変に思えるが、こういうときの定石として

一旦経路の方を固定してみて、どう操作するべきかを考えてみる

というのが大変有力ではないかと思う。

#include <iostream>
#include <vector>
#include <string>
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> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    string S;
    int K;
    cin >> S >> K;
    int N = (int)S.size();
    auto dp = make_vec<int>(N+2, N+2, K+2);
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            for (int k = 0; k <= K; ++k) {
                chmax(dp[i+1][j][k], dp[i][j][k]);
                chmax(dp[i][j+1][k], dp[i][j][k]);
                chmax(dp[i+1][j+1][k+1], dp[i][j][k] + 1);
                if (i < N && N-1-j >= 0 && S[i] == S[N-1-j])
                    chmax(dp[i+1][j+1][k], dp[i][j][k] + 1);
            }
        }
    }
    int res = 0;
    for (int k = 0; k <= K; ++k) {
        for (int i = 0; i <= N; ++i) chmax(res, dp[i][N-i][k] * 2);
        for (int i = 0; i < N; ++i) chmax(res, dp[i][N-1-i][k] * 2 + 1);
    }
    cout << res << endl;
}

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

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

AtCoder AGC 021 D - Reversed LCS (黄色, 900 点)

問題概要

制約

考えたこと

文字列を 2 つに割ってそれぞれだけ考えれば良い

(そもそも) 予め盤面や文字列を操作できるときの最適化