DDPC2016 予選 : C - アメージングな文字列は、きみが作る！

SuffixArray使い慣れなくて苦手意識があったので、本番解けて良かった。
http://discovery2016-qual.contest.atcoder.jp/tasks/discovery_2016_qual_c

問題

アルファベット小文字で構成される文字列Sがある。
この文字列に対し、以下の処理を任意に計K回実行できる。

• 1文字を削除する。
• 1文字を他のアルファベット小文字に置換する。
• アルファベット小文字1文字を任意の位置に追加する。

処理の最適な実行により得られる辞書順最小の文字列を答えよ。

解法

"a"以外の文字がK個未満なら、それらを全部消し、残り可能な限り"a"を消したのが答え。

そうでない場合、どうしても"a"以外の文字が残る。
だとすると、先頭に出来るだけ長く"a"を連ねると求める文字が得られる。

L=|S|とする。

先頭n文字S[0...(n-1)]を加工して"a"だけにし、残りS[n...(L-1)]をそのままにするケースを考える。
S[0...(n-1)]の部分でできるだけ"a"にするには、既存の"a"以外の文字をすべて"a"に置換し、余った処理回数を先頭"a"追加に費やすとよい。

各nに対し、S[n]の前に出来るだけ多くの"a"を作れる場合、そのケースが求める解となる。
ただし、複数のnにおいてS[n]の前に作れる"a"の数がタイになる場合、残りS[n...(L-1)]の大小関係がすなわち処理後の文字列の大小関係となる。
これはSuffixの大小関係を求める話なので、そのままSuffixArrayで得られるランクの最小値を求めればよい。

struct SuffixArray {
	int N; vector<int> rank,lcp,sa; string S;
	
	SuffixArray(string S) : S(S){
		int i,h=0; vector<int> tmp,tr;
		N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
		FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];
		
		for(int k=1; k<=N; k<<=1) {
			auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<((b+k<=N)?rank[b+k]:-1));};
			auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]<rank[b]):pred2(a,b);};
			int x=0;
			if(k!=1) for(i=1;i<N+1;i++) if(rank[sa[i]]!=rank[sa[x]]) sort(sa.begin()+x,sa.begin()+i,pred2), x=i;
			sort(sa.begin()+x,sa.end(),pred);
			FOR(i,N+1) tmp[sa[i]]=(i==0)?0:tmp[sa[i-1]]+pred(sa[i-1],sa[i]);
			swap(rank,tmp);
		}
		lcp.resize(N+1); tr.resize(N+1);
		FOR(i,N+1) tr[sa[i]]=i;
		FOR(i,N) {
			int j=sa[tr[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[tr[i]-1]=h;
		}
	}
};

string S;
int L,N;
int nota[301010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>N;
	L=S.size();
	
	FOR(i,L) nota[i+1]=nota[i]+(S[i]!='a');
	
	if(nota[L]<=N) {
		FOR(i,L-N) _P("a");
		_P("\n");
		return;
	}
	
	SuffixArray sa(S);
	int pos=-1;
	int numa=-1;
	FOR(i,L) if(nota[i]<=N) {
		int tnuma=i+(N-nota[i]);
		if(tnuma>numa || (tnuma==numa&&sa.rank[i]<sa.rank[pos])) {
			numa=tnuma;
			pos=i;
		}
	}
	FOR(i,numa) _P("a");
	for(i=pos;i<L;i++) _P("%c",S[i]);
	_P("\n");
}

まとめ

コンテスト正式名称がアメージングに長すぎるので、記事タイトルには略称を使っています。