これ落ちたのひどいなぁ…。
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は仮想のメモリ量で判定されるようだ…。