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

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

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

いかにも 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 の末尾の文字について
    •  x を二進法で表したときの  2^{0} の位の値が 1 のときには、 S から取って来た文字である
    •  x を二進法で表したときの  2^{1} の位の値が 1 のときには、 T から取って来た文字である
  •  X の末尾から 2 番目の文字について
    •  y を二進法で表したときの  2^{0} の位の値が 1 のときには、 S から取って来た文字である
    •  y を二進法で表したときの  2^{1} の位の値が 1 のときには、 T から取って来た文字である
  •  X の末尾から 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;
}