SRM 544 Div2 Hard AliceBobShuffle

問題

正数が書かれたカードのデッキが2つあり、2つのデッキの上からカードを任意の枚数ずつ取り出して場に積み上げていき、これを2つのデッキからカードが無くなるまで繰り返す。続いて場に積み上がったカードの上から任意枚数ずつ2つのデッキに積み戻していく。
初期状態と最終状態の2つのデッキのカードの数字がカードの積み上げ順に与えられる。このゲームの進行方向は何パターンあるか。10^9+7で割った余りを返せ。

やりかた

デッキから場に積み上げていくとき、カードの順番というのはスタックになる。スタックから取り出してデッキに積み戻していくとき、これはキューになる。
ということで初期状態の2つのカードデッキの下の方からカードを任意枚数取り出して、そのまま2つの空デッキに積んでいき、最終状態に至る方法を考えればいいので、いったん場に置くなどどいう行為は実は必要なくなる。実装的には2つのデッキの先頭から任意の枚数カードを取り出していき、最終状態のデッキとマッチさせられる数を数えていけば良く、単純なメモ化再帰でいくことができる。

以下ソース。

int memo[51][51][51][51];
const int MOD = 1000000007;

class AliceBobShuffle {
public:
  vector<int> as, bs, ae, be;
  ll rec(int a, int b, int c, int d){
    if(a == as.size() && b == bs.size() && 
       c == ae.size() && d == be.size()) return 1;
    if(memo[a][b][c][d] >= 0) return memo[a][b][c][d];
    
    ll ret = 0;
    if(a < (int)as.size() && c < (int)ae.size() && as[a] == ae[c])
      ret = (ret + rec(a + 1, b, c + 1, d)) % MOD;   
    if(a < (int)as.size() && d < (int)be.size() && as[a] == be[d]) 
      ret = (ret + rec(a + 1, b, c, d + 1)) % MOD;
    if(b < (int)bs.size() && c < (int)ae.size() && bs[b] == ae[c]) 
      ret = (ret + rec(a, b + 1, c + 1, d)) % MOD;
    if(b < (int)bs.size() && d < (int)be.size() && bs[b] == be[d]) 
      ret = (ret + rec(a, b + 1, c, d + 1)) % MOD;

    return memo[a][b][c][d] = ret;;
  }
  int countWays(vector <int> AliceStart, vector <int> BobStart, vector <int> AliceEnd, vector <int> BobEnd) {
    memset(memo, -1, sizeof(memo));
    as = AliceStart; bs = BobStart; ae = AliceEnd; be = BobEnd;
    return rec(0, 0, 0, 0) % MOD;
  }
};

何回かのTLE後AC。前回本番中に問題を見たときは完全にちんぷんかんぷんだったので、それに比べれば進化した。