DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 : D - DISCO!

まぁこれは解ける人多くてもそんなもんかな…。
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d

問題

文字列Sが与えられる。
以下のクエリに答えよ。

• 区間[L..R]が与えられる。S[L..R]のsubsequenceのうち、"DISCO"となるものは何通りか。

解法

個々のクエリを考えると、"DISCO"のうち何文字マッチ済みか、0～5文字の6通りの状態を持ってDPすることになる。
よって、SegTreeに6*6の状態遷移のMatrixを持たせ、区間を併合する際にその積を取るようにすれば、S[L...R]に対応する状態遷移の組み合わせを容易に列挙できる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V def;
	V comp(V l,V r){
		V ret(36,0);
		int x,y,z;
		FOR(x,6) for(y=x;y<6;y++) for(z=y;z<6;z++) {
			ret[x*6+z]+=l[x*6+y]*r[y*6+z];
		}
		return ret;
	};
	
	SegTree_1(){
		def.resize(36);
		int i;
		FOR(i,6) def[i*6+i]=1;
		val=vector<V>(NV*2,def);
	};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<vector<unsigned int>,1<<20> st;
int N,Q;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>Q;
	N=S.size();
	FOR(i,N) {
		st.val[i+(1<<20)]=st.def;
		if(S[i]=='D') st.val[i+(1<<20)][0*6+(0+1)]=1;
		if(S[i]=='I') st.val[i+(1<<20)][1*6+(1+1)]=1;
		if(S[i]=='S') st.val[i+(1<<20)][2*6+(2+1)]=1;
		if(S[i]=='C') st.val[i+(1<<20)][3*6+(3+1)]=1;
		if(S[i]=='O') st.val[i+(1<<20)][4*6+(4+1)]=1;
	}
	
	for(i=(1<<20)-1;i>=1;i--) {
		st.val[i]=st.comp(st.val[i*2],st.val[i*2+1]);
	}
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		auto a=st.getval(L,R);
		cout<<a[5]<<endl;
	}
}

まとめ

Cに比べても迷う部分は少ないせいか、正答者多いね。