CROC 2016 Elimination Round : E. Intellectual Inquiry

本番解けて良かった。
http://codeforces.com/contest/655/problem/E

問題

アルファベットの先頭K種類を用いて作られた文字列Sを考える。
Sのうち先頭M文字はすでに与えられている。
残りN文字は任意に作成できる。

Sの部分文字列(不連続も可)の種類が最大になるようにN文字分を選択したとき、種類の数を答えよ。

解法

まず任意に付け加える部分は除き、部分文字列の種類の数え上げ手法を考える。
これは以下の問題が参考になる。
G - 辞書順

以下の変数を考える。
dp[n] := S[1...n]の部分文字列のうち、S[n]が必ず末尾になるようなものの組み合わせ数
f(n,c) := S[n]の次に登場する文字cの最寄りの位置

dp[n]は後ろから以下のDPを行うことで求めることができる。(+1はn文字目が末尾となるケース。)
dp[n] := sum_c(dp[f(n,c)]) + 1

あとはN文字をどう作成するかの問題である。
いくつか実験してみると、「手前に登場する文字のうち、位置が最も遠い文字」を順次くっつけていくとdp[0]が最大となる。

int N,M,K;
string T;
ll dp[2002020];
ll mo=1000000007;

ll hoge(string S) {
	int nn[26],i,j;
	int L=S.size();
	FOR(i,K) nn[i]=L+1;
	
	ll ret=0;
	for(i=L;i>=0;i--) {
		dp[i]=1;
		FOR(j,K) dp[i]+=dp[nn[j]];
		dp[i]%=mo;
		ret+=dp[i];
		if(i) nn[S[i-1]]=i;
	}
	
	return dp[0];
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>T;
	M=T.size();
	T+=string(N,'a');
	FORR(r,T) r-='a';
	int pre[26];
	FOR(i,K) pre[i]=-1;
	FOR(i,M) pre[T[i]]=i;
	
	FOR(i,N) {
		x=0;
		FOR(j,K) if(pre[j]<pre[x]) x=j;
		T[M+i]=x;
		pre[x]=M+i;
	}
	cout<<hoge(T)<<endl;
	
	
}

まとめ

数え上げパートは知識として知らなかったが、なんとか本番に思いつけた。
N文字の追加ルールも合わせ、本番中に解ききれて良かった。