Good Bye 2016 : E. New Year and Old Subsequence

本番解法は思いついたものの実装時間切れ。そもそも実装が悪くてTLEしてたのでどのみちダメだけど。
http://codeforces.com/contest/750/problem/E

問題

数字で構成された文字列Sが与えられる。
Sに対しQ個のクエリに答えよ。

各クエリはSの連続部分文字列S'=S[A..B]を指す。
S'中、いくつか文字を削除し、(連続しなくてもよい)部分列として2017を含み、かつ2016は含まないようにしたい。
最小何文字文字を消せばよいか答えよ。

解法

SegTreeで解く。
Sの部分文字列に対し、2017を含むかどうかを状態遷移で考える。
状態は2017と0～4文字マッチした後かどうかの5とおりある。
このうち201または2017までマッチした状態で6が登場してはいけない。

以下の状態を考える。
f(L,R,i,k) := 部分文字列S[L..R]において、状態i→kへの存在するか、また存在するなら削除する最小文字列数

f(A,B,0,4)が求める解である。
このf(L,R,i,k)は以下の要領でより小さい部分文字列の結果を合成して得られるので、SegTreeを使えば任意の部分文字列に対しO(log|S|)でf(A,B,0,4)を求められる。
f(L,R,i,k) = min(f(L,M,i,j)+f(M,R,j,k))

int N,Q;
string S;

const int NP=5;
struct mat { int x[NP][NP];};

const int NV=1<<18;
mat val[NV*2],def,ze;

mat conv(const mat& b,const mat& c) {
	mat a=def;
	int i,j,k;
	FOR(i,NP) for(k=i;k<NP;k++) for(j=k;j<NP;j++) a.x[i][j]=min(a.x[i][j],b.x[i][k]+c.x[k][j]);
	return a;
}

mat getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
	if(r<=x || y<=l) return ze;
	if(x<=l && r<=y) return val[k];
	return conv(getval(x,y,l,(l+r)/2,k*2) ,getval(x,y,(l+r)/2,r,k*2+1));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,NP) FOR(j,NP) def.x[i][j]=1<<28;
	ze = def;
	FOR(i,NP) ze.x[i][i]=0;
	FOR(i,NV) val[i+NV]=ze;
	
	FOR(i,N) {
		if(S[i]=='2') {
			val[i+NV+1].x[0][0]=1;
			val[i+NV+1].x[0][1]=0;
		}
		else if(S[i]=='0') {
			val[i+NV+1].x[1][1]=1;
			val[i+NV+1].x[1][2]=0;
		}
		else if(S[i]=='1') {
			val[i+NV+1].x[2][2]=1;
			val[i+NV+1].x[2][3]=0;
		}
		else if(S[i]=='7') {
			val[i+NV+1].x[3][4]=0;
		}
		else if(S[i]=='6') {
			val[i+NV+1].x[3][3]=1;
			val[i+NV+1].x[4][4]=1;
		}
	}
	
	for(i=NV-1;i>=1;i--) val[i]=conv(val[i*2],val[i*2+1]);
	FOR(i,Q) {
		int A,B;
		cin>>A>>B;
		auto v=getval(A,B+1).x[0][4];
		if(v>=1<<28) v=-1;
		_P("%d\n",v);
	}
	
	
}

まとめ

本番15*15の状態遷移を考えてしまったのでどのみちTLEだった。