ICPCのF
そういえばICPCのF問題です。
最初は枝刈りかと思いましたが、チームメイトに悪質なケースを考えてもらったところ、
aかb : 11111...11 変換: 11 -> 1 11 -> 2 .... 11 -> 30
とかだと30^12通りくらいは出来るのでダメだということが分かり、強多項式だと考える。
変換される数列の元の数列上での区間は交差しないので、最初にローテーションを全部決め打ちすれば良いことに気づき、一致判定は典型なDPで解けそうで、ある区間をどの文字に変換できるかを調べるパートは何となく区間DPっぽいことをすれば良さそうな気がしたので考えたら解けた。
だけどちょっと時間が足りなかった・・・さすがにEのデバッグに専念すべきだった。
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; int n, m, r; int a[26], b[26]; int k[61], x[61][11], y[61]; void rotate(int c[26], int len){ rep(i,len-1) swap(c[i],c[i+1]);} int dp[26][26]; bool rdp[26][11]; vector<int> ad[31][26]; vector<int> bd[31][26]; void rng(vector<int> d[31][26], int len, int i, int j, int h){ rep(o,len+1)rep(p,k[h]+1) rdp[o][p] = false; rdp[j][0] = true; for(int o = j; o < j+i; o++)rep(q,k[h]){ if(!rdp[o][q]) continue; rep(p,d[x[h][q]][o].size()) rdp[d[x[h][q]][o][p]][q+1] = true; } if(rdp[j+i][k[h]]) d[y[h]][j].push_back(i+j); } void calc(int len, vector<int> d[31][26], int c[26]){ rep(j,31)rep(i,len) d[j][i].clear(); rep(i,len) d[c[i]][i].push_back(i+1); for(int i = 2; i <= len; i++)rep(j,len-i+1)rep(h,r) rng(d,len,i,j,h); } int sol(){ calc(n,ad,a); calc(m,bd,b); rep(i,n+1)rep(j,m+1) dp[i][j] = -100; dp[0][0] = 0; rep(i,n)rep(j,m){ if(dp[i][j] == -100) continue; rep(h,31)rep(o,ad[h][i].size())rep(p,bd[h][j].size()){ dp[ad[h][i][o]][bd[h][j][p]] = max(dp[ad[h][i][o]][bd[h][j][p]],dp[i][j]+1); } } return dp[n][m]; } int main(){ while(cin>>n>>m>>r, n){ rep(i,n) cin >> a[i]; rep(i,m) cin >> b[i]; rep(i,r){ cin >> k[i]; rep(j,k[i]) cin >> x[i][j]; cin >> y[i]; } int ans = 0; rep(i,n){ rep(j,m){ ans = max(ans,sol()); rotate(b,m); } rotate(a,n); } cout << (ans==0?-1:ans) << endl; } return 0; }