AtCoder ARC #081 : E - Don't Be a Subsequence

Fでグダった。
https://beta.atcoder.jp/contests/arc081/tasks/arc081_c

問題

アルファベット小文字で構成される文字列Sが与えられる。

同じくアルファベット小文字で構成される文字列のうち、Sの部分列となる最短の文字列を答えよ。
同じ長さの候補があるならば辞書順最小値を求めよ。

解法

部分列の数え上げDPを応用する。
S中の各iについて、そのS[i]を先頭とする部分文字列のうち、問題文どおり最短もしくは辞書順最短のものを考えよう。

S[i]の次にa～zを選んだ場合、S[i]の後にある最寄りのindexに遷移することになる。
よって、a～zのうち、遷移後の同上の文字列が最短もしくは辞書順最小となるものを選ぼう。
S[i]をiの大きな順に埋めていけばよい。

int N;
string S;
int nex[202020][26];
int ne[26];
int len[202020],ta[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	FOR(i,26) ne[i]=nex[N+1][i]=N+1;
	for(i=N;i>=0;i--) {
		len[i]=202020;
		FOR(j,26) {
			nex[i][j]=ne[j];
			x = len[ne[j]];
			if(x<len[i]) {
				len[i]=x;
				ta[i]=j;
			}
		}
		len[i]++;
		if(i) ne[S[i-1]-'a']=i;
	}
	
	string R;
	int cur=0;
	while(cur!=N+1) {
		R+='a'+ta[cur];
		cur=nex[cur][ta[cur]];
	}
	
	cout<<R<<endl;
}

まとめ

Eはちょっと手こずった程度で済んだのだけどね。