yukicoder : No.1845 Long Substrings

参加が遅くほとんど解けず。
https://yukicoder.me/problems/no/1845

問題

アルファベット小文字で構成されるとても長い文字列が、RLE形式で文字S[i]がA[i]個連続する、という形で与えられる。
Sの(不連続でもよい)部分列としてありうる文字列は、重複を除いて何通りか。

解法

部分列を数え上げる問題なので、a～zを貪欲にできるだけ手前から拾っていくことを考える。

dp(i) := 圧縮後でi個目の要素のうち、先頭1文字を拾う組み合わせ
next(i,c) := 圧縮後でi個目以降の要素のうち、文字cを持つ添え字の最小値
とする。

S[i]を最低1個、最高A[i]個拾った後別の文字を後ろにくっ付けるわけだが、S[i]以外をくっ付ける場合はS[i]をA[i]個以下何個拾った後に遷移してもよい。
ただし、S[i]と同じ文字を他の要素で拾い続ける場合、S[i]をA[i]個拾っていないと遷移できない。

int N;
int A[202020];
string S;

ll dp[202020];
int nex[202020][26];
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	cin>>S;
	FOR(i,26) nex[N][i]=N;
	for(i=N-1;i>=0;i--) {
		S[i]-='a';
		FOR(j,26) nex[i][j]=nex[i+1][j];
		nex[i][S[i]]=i;
	}
	FOR(i,26) if(nex[0][i]<N) dp[nex[0][i]]++;
	ll ret=0;
	FOR(i,N) {
		(ret+=dp[i]*A[i])%=mo;
		FOR(j,26) {
			if(S[i]==j) {
				(dp[nex[i+1][j]]+=dp[i])%=mo;
			}
			else {
				(dp[nex[i+1][j]]+=dp[i]*A[i])%=mo;
			}
		}
	}
	cout<<ret<<endl;
}

まとめ

RLEというとBMPファイルの印象強いんだよな。
自分でデコードしたことはないけど。