AOJ 1191 - Rotate and Rewrite
解法
こういう問題に対する典型的な発想として、一文字ずつ構成していく、というものがある。
つまり、A の先頭位置と B の先頭位置を決めうった後、一文字ずつ作っていって、A, B それぞれをちょうど使い切れたら、それが答えの候補になる。
このために dp をする。dp は2段階からなる。
先に2段階目の dp を考える。A, B の先頭位置を s1, s2 と決めうつと、
dp[i][j] := A[s1..s1+i), B[s2...s2+j) を使い切って一致させるときの最大長
となる。求めたい答えは dp[n][m] である。
遷移式は、各 l1, l2 に対して
もし A[s1+i...s1+i+l1) と b[s2+j...s2+j+l2) を使い切って同じ文字にできるなら
dp[i + l1][j + l2] = max(dp[i + l1][j + l2], dp[i][j] + 1)
となる。条件部分を判定するために、別の dp が必要。
これは A, B のどちらについても同じなので、A だけ考えると
can_make[l][r][k] := A[l..r) を使い切って値 k に一致させられるか？
である。これを求めるために補助テーブル
r_dp[l][r][i][j] := A[l..r) まで使い切って、書き換えルール i の j 文字目まで一致させられるか？
を同時に作っていく。これによって、遷移は
ある k があって、r_dp[l][k][i][j - 1] かつ A[k..r) を使い切ってルール i の j 文字目にできるならば
r_dp[l][r][i][j] = true
とかける。この後、r_dp の更新を can_make に伝搬させるため
書き換えルール i について、A[l..r) から x1, ..., xk をすべて作れたら
can_make[l][r][y] = true
と更新する。
更にその後、can_make の更新を r_dp に伝搬させるため、
書き換えルール i の一文字目が A[l..r) を使い切って作れるなら
r_dp[l][r][i][1] = true
と更新する。
これを r - l の小さい方からやっていくと求まる。
あとは can_make を使って最初の dp を行えば解ける。
計算量は O(n^3m^3 * 30 + (n^3 + m^3)r*10) ぐらいでヤバ過ぎるが、適当に枝刈りを入れると 2sec ぐらいで通った。
critical な枝刈り部分はソースコードのコメントに書いた。
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> std::vector<T> table(int n, T v) { return std::vector<T>(n, v); } template <class... Args> auto table(int n, Args... args) { auto val = table(args...); return std::vector<decltype(val)>(n, std::move(val)); } constexpr int max_a = 30; constexpr int max_k = 10; auto calc_can_make(vector<int> const& a, vector<vector<int>> const& xs, vector<int> const& ys) { const int n = a.size() / 2, r_sz = xs.size(); auto can_make = table(a.size(), a.size(), max_a + 1, false); // r_dp[i][j][k][l] := can match a[i..j) with xs[k][0..l) ? auto r_dp = table(a.size(), a.size(), r_sz, max_k + 1, false); for(int i = 0; i + 1 < n * 2; ++i) { can_make[i][i + 1][a[i]] = true; } for(int i = 0; i < n; ++i) { for(int j = 0; j < r_sz; ++j) { r_dp[i][i][j][0] = true; } } for(int len = 1; len <= n; ++len) { for(int l = 0; l + len < 2 * n; ++l) { const int r = l + len; for(int i = 0; i < r_sz; ++i) { for(int j = 1; j <= (int)xs[i].size(); ++j) { for(int k = l; k < r; ++k) { if(r_dp[l][k][i][j - 1] && can_make[k][r][xs[i][j - 1]]) { r_dp[l][r][i][j] = true; } } } } for(int i = 0; i < r_sz; ++i) { if(r_dp[l][r][i][xs[i].size()]) { can_make[l][r][ys[i]] = true; } } for(int i = 0; i < r_sz; ++i) { if(can_make[l][r][xs[i][0]]) { r_dp[l][r][i][1] = true; } } } } return can_make; } int main() { int n, m, r; while(cin >> n >> m >> r, n) { vector<int> a(n * 2), b(m * 2); vector<vector<int>> xs(r); vector<int> ys(r); for(int i = 0; i < n; ++i) { cin >> a[i]; a[i + n] = a[i]; } for(int i = 0; i < m; ++i) { cin >> b[i]; b[i + m] = b[i]; } for(int i = 0; i < r; ++i) { int k; cin >> k; xs[i].resize(k); for(auto& x : xs[i]) cin >> x; cin >> ys[i]; } auto can_make_a = calc_can_make(a, xs, ys); auto can_make_b = calc_can_make(b, xs, ys); int ans = -1; for(int s1 = 0; s1 < n; ++s1) { for(int s2 = 0; s2 < m; ++s2) { vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1)); dp[0][0] = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if(dp[i][j] == -1) continue; for(int k = 1; k <= 30; ++k) { for(int l1 = 1; l1 <= n - i; ++l1) { if(!can_make_a[s1 + i][s1 + i + l1][k]) continue; // critical for(int l2 = 1; l2 <= m - j; ++l2) { if(can_make_a[s1 + i][s1 + i + l1][k] && can_make_b[s2 + j][s2 + j + l2][k]) { dp[i + l1][j + l2] = max(dp[i + l1][j + l2], dp[i][j] + 1); } } } } } } ans = max(ans, dp[n][m]); } } cout << ans << endl; } }
感想
いわれてみれば確かになあという感じなんだけど全く見えなかった。
やりたいことのゴールから逆算していくと見えるのかなあ。一生解ける気がしない。
あとオーダーヤバスギ（国内予選だからまあ良いんだろうけど…）。
