TopCoder SRM 709 Div1 Medium Softmatch、Div2 Hard Softmatchd2

想定解をまだ理解していない。
https://community.topcoder.com/stat?c=problem_statement&pm=14531
https://community.topcoder.com/stat?c=problem_statement&pm=14542

問題

"ab"で構成される文字列Sと、いくつかのマッチングパターンがある。

マッチングパターンは0～3の文字で構成される文字列であり、以下の文字にマッチする。

• 'a'は0か1にマッチする。
• 'b'は0か2にマッチする。
• 'A'は2か3にマッチする。
• 'B'は1か3にマッチする。

Sの各文字を大文字小文字任意に選択できるとき、マッチングパターンにマッチする回数の最大値を求めよ。

解法

マッチングのパターンが少ないこともあり、Aho-Corasickの要領で、「(i番目のパターンがj文字までマッチした)という情報の集合」を愚直に管理していくと通ってしまった。
文字のマッチング条件の厳しさと、パターンの少なさから状態があまり多くないことが要因と思われる。

class Softmatch {
	public:
	int count(string S, vector <string> patterns) {
		vector<pair<int,vector<int>>> from,to;
		int N=patterns.size();
		int i,st;
		
		from.clear();
		from.push_back({0,vector<int>()});
		FORR(c,S) {
			
			sort(ALL(from));
			from.erase(unique(ALL(from)),from.end());
			to.clear();
			
			FORR(r,from) {
				
				string pat[4]={"01","23","02","13"};
				FOR(st,2) {
					char c0=pat[st+(c-'a')*2][0];
					char c1=pat[st+(c-'a')*2][1];
					
					int cnt=r.first;
					vector<int> nex;
					
					FOR(i,N) if(patterns[i][0]==c0 || patterns[i][0]==c1) {
						if(patterns[i].size()==1) cnt++;
						else nex.push_back(i*100+1);
					}
					FORR(p,r.second) if(patterns[p/100][p%100]==c0 || patterns[p/100][p%100]==c1) {
						if(patterns[p/100].size()==p%100+1) cnt++;
						else nex.push_back(p+1);
					}
					
					to.push_back({cnt,nex});
				}
			}
			swap(from,to);
		}
		int ma=0;
		FORR(r,from) ma=max(ma,r.first);
		
		return ma;
	}
}

まとめ

こんな適当解法でMed通ったスコアが4番目だったけどいいのかなぁ…。