Codeforces #396 Div2 C. Mahmoud and a Message

日程を間違えて出そびれたんだけど、このセットなら出なくてよかったな…。
http://codeforces.com/contest/766/problem/C

問題

文字列Sと、各アルファベットcに対応した整数値A[c]が与えられる。
Sをいくつかの部分文字列の連結の形で表したい。
その際、部分文字列にcが含まれている場合、その部分文字列はA[c]以下でなければならない。

以下を求めよ。

• 分割の仕方は何通りあるか。
• 登場しうる最長の部分文字列は何文字か。
• 最小で何個の部分文字列に分割することができるか。

解法

以下の2値を愚直に更新していくだけ。
S[(i+1)...j]を条件を満たす文字列なら、f(i+j),g(i+j)を更新していこう。
ついでに最長の部分文字列も求めておくとよい。

f(i) := 先頭からi文字目までを何通りの分割で表現できるか
g(i) := 先頭からi文字目までを最小何個の分割で表現できるか

int N;
string S;
int A[26];
ll dp[1010];
int mis[1010];
ll mo=1000000007;
int ma=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,26) cin>>A[i];
	FOR(i,N+1) mis[i]=1010;
	
	dp[0]=1;
	mis[0]=0;
	FOR(i,N) {
		int B[26];
		FOR(j,26) B[j]=A[j];
		int mi=10101;
		for(j=i;j<N;j++) {
			mi=min(mi,A[S[j]-'a']);
			if(j-i+1>mi) break;
			ma=max(ma,j-i+1);
			(dp[j+1]+=dp[i])%=mo;
			mis[j+1]=min(mis[j+1],mis[i]+1);
		}
	}
	
	cout<<dp[N]<<endl;
	cout<<ma<<endl;
	cout<<mis[N]<<endl;
	
}

まとめ

うーん。