yukicoder : No.1609 String Division Machine

なるほど。
https://yukicoder.me/problems/no/1609

問題

文字列Sを以下のアルゴリズムで分割する。

• 以下をSが空になるまで繰り返す。
  • Sの部分列のうち、辞書順最大のものを求める。
  • Sから上記部分列を削除する。

Sの分割数とは、上記処理を繰り返す回数とする。

ここで、文字列Sが与えられる。
Sの一部は未確定である。
以下を満たすようなSを求めよ。

• 分割数が最小
• その中で辞書順最小

解法

1回の処理で取り除かれる文字列は、常にアルファベット降順になっている。
これを踏まえ、以下のようにするとよい。

• まず?を無視して分割数を求めよう。Sの未確定部分が何であれ、これより分割数を下げることはできない。
• そのうえで?の中身を求める。上記アルゴリズムで、最後の周回の時に?の部分が全部消えるようにしよう。
  • アルファベット降順の条件から、?の部分は一意に決まる。

int N;
string S;

set<int> C[26];
int step[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) if(S[i]!='?') {
		C[S[i]-'a'].insert(i);
	}
	MINUS(step);
	int cur=0;
	while(1) {
		int pos=-1;
		while(1) {
			for(j=25;j>=0;j--) {
				auto it=C[j].lower_bound(pos);
				
				if(it!=C[j].end()) {
					step[*it]=cur;
					pos=*it;
					C[j].erase(it);
					break;
				}
			}
			if(j<0) break;
		}
		if(pos==-1) break;
		cur++;
	}
	cur--;
	char c='a';
	for(i=N-1;i>=0;i--) {
		if(S[i]=='?') S[i]=c;
		if(step[i]==cur) c=max(c,S[i]);
	}
	
	cout<<S<<endl;
	
	
}

まとめ

Editorialの解法賢いな。