読者です 読者をやめる 読者になる 読者になる

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;
}