TopCoder SRM 723 Div1 Medium BuffaloBuffaloBuffalo

これ落ちたのひどいなぁ…。
https://community.topcoder.com/stat?c=problem_statement&pm=14731

問題

ある文字列Aが複数の文字列のinterleaveであるとは、A中にそれらの文字列を部分列として分解できることを意味する。
ここでワイルドカード"?"を含むN文字の文字列Sが与えられる。
この文字列Sが、複数の"buffalo"のinterleaveとなりうるか、その場合分解の仕方を答えよ。

解法

buffaloが7文字なので、Nが7の倍数でなければならないのは明らか。
後は「先頭k文字までマッチしたものが何個ずつあるか」という状態をもとに状態遷移しながらDPするだけ。

やり方が悪いとO(N^8)程度かかりTLEするので次元を落とす必要がある。
いくつか方法があるようだ。

• 真ん中にffとfが2回続くのでこれを同一視する(以下のコードはそうなっている)
• マッチしたものの個数があれば、マッチ済みの文字数を特定できることを用い状態を減らす。

int mo=1000000007;
int dp[15][15][31][15][15][15];
vector<vector<int>> V;

void add(int& a,int&b) {
	a+=b;
	if(a>=mo) a-=mo;
}

class BuffaloBuffaloBuffalo {
	public:
	int count(string P) {
		int N=P.size(),M=N/7;
		
		if(N%7) return 0;
		ZERO(dp);
		
		dp[N/7][0][0][0][0][0]=1;
		FORR(s,P) {
			int a,b,c,d,e,f;
			for(f=M;f>=0;f--) for(e=M-f;e>=0;e--) for(d=M-f-e;d>=0;d--) for(c=2*(M-d-e-f);c>=0;c--) for(b=M-c/2-d-e-f;b>=0;b--) for(a=M-b-c/2-d-e-f;a>=0;a--) {
				int x=dp[a][b][c][d][e][f];
				if(x==0) continue;
				if((s=='b' || s=='?') && a) add(dp[a-1][b+1][c][d][e][f],x);
				if((s=='u' || s=='?') && b) add(dp[a][b-1][c+2][d][e][f],x);
				if((s=='f' || s=='?') && c) {
					if(c%2) add(dp[a][b][c-1][d+1][e][f],x);
					else V.push_back({a,b,c-1,d,e,f,x});
				}
				if((s=='a' || s=='?') && d) add(dp[a][b][c][d-1][e+1][f],x);
				if((s=='l' || s=='?') && e) add(dp[a][b][c][d][e-1][f+1],x);
				if((s=='o' || s=='?') && f) {
					V.push_back({a,b,c,d,e,f-1,x});
				}
				dp[a][b][c][d][e][f]=0;
			}
			FORR(v,V) {
				add(dp[v[0]][v[1]][v[2]][v[3]][v[4]][v[5]],v[6]);
			}
			V.clear();
		}
		return dp[0][0][0][0][0][0];
	}
}

まとめ

解法はあっていたのに、未使用変数でMLEした。
Codeforcesとかでは実メモリ使用量で判定されるが、SRMは仮想のメモリ量で判定されるようだ…。