TopCoder SRM 811 : Div1 Hard MonotoneStrings

なんか先日のABCみたいな問題だな。
https://community.topcoder.com/stat?c=problem_statement&pm=17131&rd=18802

問題

ワイルドカードを含む文字列パターンが与えられる。
(ワイルドカードは、任意の文字1・10・100文字相当分の3種類がある)

S種類の文字種が使える文字列のうち、この文字列パターンに一致する文字列で、かつmonotoneなものは何通りか。
文字列がmonotoneとは、同じ種類の文字が文字列中で常に連結していることを示す。

解法

まずmonotoneの条件に合致しないものをはじく。
各文字種について、2回以上登場するものがあれば、その間をその文字で埋めよう。
もし同じ場所を埋めるべき文字種が2つ以上衝突するなら解なしである。

この処理を行うと、同じ文字種の間は常にその文字で埋まるため、同種の文字の間にワイルドカードが残ることはない。
文字列パターンのうち、10文字・100文字相当のワイルドカードは、実際に10文字・100文字に展開してしまおう。このパターンをPとする。
以後、以下のDPを行おう。
dp(n, s, c) := 文字列のうち先頭n文字を決めたとき、未使用の文字種はs種類で、直前の文字が下記のうちc種類目であるような状態における組み合わせ

• c=0: n文字目は、Pのn文字目前に出てくる直前の確定済み文字と同じ
• c=1: n文字目は、Pに出てこない確定済み文字と同じ
• c=2: n文字目は、Pのn文字目以降に出てくる最初の確定済み文字と同じ

文字列パターン中にワイルドカード意外にT通りの文字種があったとき、dp(0,S-T,1)から初めて、dp(|P|,*,0)+dp(|P|,*,1)が解となる。

ll from[404][3];
ll to[404][3];
const ll mo=1000000007;

class MonotoneStrings {
	public:
	int count(int S, string pattern) {
		string T=pattern;
		int i,N=pattern.size(),j,x;
		FOR(i,N) {
			if(pattern[i]=='?') continue;
			if(pattern[i]=='+') continue;
			if(pattern[i]=='-') continue;
			FOR(j,i) if(pattern[j]==pattern[i]) break;
			if(j==i) continue;
			for(x=j+1;x<i;x++) {
				T[x]=T[i];
				if(pattern[x]=='?') continue;
				if(pattern[x]=='+') continue;
				if(pattern[x]=='-') continue;
				if(pattern[x]!=pattern[i]) return 0;
			}
		}
		
		vector<int> C;
		string W;
		int lef=S;
		FORR(c,T) {
			if(c=='?'||c=='+'||c=='-') {
				W+=c;
			}
			else {
				if(W.size()&&W.back()==c) continue;
				C.push_back(W.size());
				W+=c;
				lef--;
			}
		}
		
		ZERO(from);
		from[lef][1]=1;
		FOR(j,W.size()) {
			int num=0;
			if(W[j]=='?') num=1;
			if(W[j]=='-') num=10;
			if(W[j]=='+') num=100;
			if(num==0) {
				FOR(x,S+1) {
					from[x][0]=(from[x][0]+from[x][1]+from[x][2])%mo;
					from[x][1]=from[x][2]=0;
				}
			}
			else {
				if(j==0) {
					ZERO(from);
					if(lef) from[lef-1][1]=lef;
					from[lef][2]=1;
					num--;
				}
				while(num--) {
					FOR(i,S+1) {
						// 1->2
						from[i][2]+=from[i][1];
						if(from[i][2]>=mo) from[i][2]-=mo;
						if(i) {
							// 0->1
							// 1->1
							(from[i-1][1]+=i*(from[i][0]+from[i][1]))%=mo;
						}
						// 0->2
						from[i][2]+=from[i][0];
						if(from[i][2]>=mo) from[i][2]-=mo;
						
						//cout<<num<<" "<<i<<" "<<from[i][0]<<" "<<from[i][1]<<" "<<from[i][2]<<endl;
					}
				}
			}
			
			
			
		}
		
		ll ret=0;
		FOR(i,S+1) ret+=from[i][0]+from[i][1];
		
		return ret%mo;
		
	}
}

まとめ

ワイルドカードを愚直に展開しても間に合うのびっくり。
もっと二項係数とか使わされるのかと思ってた。