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"); }
まとめ
コンテスト正式名称がアメージングに長すぎるので、記事タイトルには略称を使っています。