いかにも JOI にありがちな添字の持ち方をする DP！

問題へのリンク

問題概要

英小文字と英大文字からなる長さ $N$ の文字列 $S$ と、長さ $M$ の文字列 $T$ が与えられる。また 0 以上 3 以下の整数 $K$ が与えられる。

次の条件を満たす文字列 $X$ の長さの最小値を求めよ。

$X$ は、英小文字と英大文字からなる
$X$ は、文字列 $S$ を部分文字列 (連続でなくてよい) とする
$X$ は、文字列 $T$ を部分文字列 (連続でなくてよい) とする
$X$ に含まれる同じ文字の間には、 $K$ 個以上の別の文字がある

制約

$1 \le N, M \le 500$
$0 \le K \le 3$

考えたこと

いかにも DP っぽい。基本的には次のような DP を考えたくなる。

dp[i][j] ← 文字列 $S$ の先頭から $i$ 文字分を部分列にもち、文字列 $T$ の先頭から $j$ 文字分を部分列にもつような文字列 $X$ の長さの最小値

しかし、これだと「同じ文字の間には、 $K$ 個以上の別の文字がある」という条件を満たせるかどうかが分からない。そこで、文字列 $X$ の末尾 $K$ 文字分の情報を配列 dp に持たせることにしよう。

さらに、その末尾 $K$ 文字分の情報について、各文字の情報としては、アルファベット文字 52 通りではなく、

$S$ から取って来たものであるか
$T$ から取って来たものであるか

のみに着目した 4 通りで十分である。そこで、次の配列 dp を考える ( $K \le 3$ より、付加情報は 3 次元分を持っている)。

dp[i][j][x][y][z] ← 文字列 $S$ の先頭から $i$ 文字分を部分列にもち、文字列 $T$ の先頭から $j$ 文字分を部分列にもつような文字列 $X$ のうち、次の条件を満たす文字列の長さの最小値

の末尾の文字について
- $x$ を二進法で表したときの $2^{0}$ の位の値が 1 のときには、 $S$ から取って来た文字である
- $x$ を二進法で表したときの $2^{1}$ の位の値が 1 のときには、 $T$ から取って来た文字である
の末尾から 2 番目の文字について
- $y$ を二進法で表したときの $2^{0}$ の位の値が 1 のときには、 $S$ から取って来た文字である
- $y$ を二進法で表したときの $2^{1}$ の位の値が 1 のときには、 $T$ から取って来た文字である
の末尾から 3 番目の文字について
- $z$ を二進法で表したときの $2^{0}$ の位の値が 1 のときには、 $S$ から取って来た文字である
- $z$ を二進法で表したときの $2^{1}$ の位の値が 1 のときには、 $T$ から取って来た文字である

なお、この配列 DP を更新しようとするとき、ループが生じることがある。よって、for 文を用いるのではなく、幅優先探索の要領で更新していくようにしよう。

計算量は $O(NM 4^{K})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 510;
int dp[MAX][MAX][4][4][4];

int main() {
    int N, M, K;
    string S, T;
    cin >> N >> M >> K >> S >> T;
    
    // S から i 文字、T から j 文字とっていて、最後 3 文字のステータスが sts である状態で
    // 文字 c をくっつけられるか
    auto check = [&](char c, int i, int j, int x, int y, int z) -> bool {
        if (c == '?') return true;
        int pi = i-1, pj = j-1;
        vector<int> vec({x, y, z});
        for (int k = 0; k < K; ++k) {
            if (vec[k] & (1 << 0)) if (pi >= 0 && c == S[pi--]) return false;
            if (vec[k] & (1 << 1)) if (pj >= 0 && c == T[pj--]) return false;
        }
        return true;
    };
    
    // i, j, 最後 k, その前 l, さらにその前 m
    memset(dp, -1, sizeof(dp));
    
    // 0: ?, 1: from S, 2: from T
    int res = 0;
    dp[0][0][0][0][0] = 0;
    queue<array<int, 5>> que;
    que.push({0, 0, 0, 0, 0});
    while (!que.empty()) {
        auto [i, j, x, y, z] = que.front();
        que.pop();
        
        if (i == N && j == M) {
            res = dp[i][j][x][y][z];
            break;
        }
        
        // 次の文字の候補
        vector<char> nc({'?'});
        if (i < N) nc.push_back(S[i]);
        if (j < M) nc.push_back(T[j]);
        
        // 文字 c を新たに加える
        for (auto c : nc) {
            if (check(c, i, j, x, y, z)) {
                int ni = i, nj = j, nx = 0;
                if (ni < N && S[ni] == c) {
                    ++ni;
                    nx |= 1 << 0;
                }
                if (nj < M && T[nj] == c) {
                    ++nj;
                    nx |= 1 << 1;
                }
                if (dp[ni][nj][nx][x][y] == -1) {
                    dp[ni][nj][nx][x][y] = dp[i][j][x][y][z] + 1;
                    que.push({ni, nj, nx, x, y});
                }
            }
        }
    }
    cout << res << endl;
}

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

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

JOIG 2024 E - 名前 (難易度 9)

問題概要

制約

考えたこと

コード