ARC081 E : Don't Be a Subsequence(600)
作成日：2017.08.24
最終更新日：2017.08.24
問題概要
英小文字からなる文字列$A$が与えられる。
$A$の部分列でない英小文字からなる文字列で最も短いもののうち辞書順最小のものを求めよ。
制約
$1 \leq |A| \leq 2 \times 10^5$
考え方
答えは空文字列になり得ないから、答えとなる文字列は1文字が最短である。
こうなるのは文字列中に含まれていない英小文字が存在する時のみであることはすぐに分かる。
逆に答えとなる文字列が2文字以上となるのは、文字列中にすべての英小文字が含まれている時であることも分かる。
答えとなる文字列が2文字の時を考える(1文字でない条件は満たすとする)。
その文字列が$"a*"$である時、文字列$A$中の$'a'$の後に$'*'$は存在しないことが条件より分かる。
逆に答えが$"a*"$でないのは文字列$A$中の$'a'$で後にすべての英小文字が含まれている時である。
同様に考えると、ある文字の後ろにすべての英小文字が含まれている時は、その文字が答えの1文字目にはなり得ない。
すなわち、後ろから見ていきすべての英小文字が1回以上現れた地点より前に現れない英小文字のうち辞書順最小のものが答えの文字列の一文字目になり、
2文字目は文字列$A$中の1文字目の英小文字の後に現れない英小文字のうち辞書順最小のものである。
答えとなる文字列が3文字以上の時も再帰的に考えることで解くことができる。
ソースコード
マクロ等はこちら
const int MC = 200010;
char A[MC];
int b[MC];
int c[MC];
int main(){
scanf("%s" , A);
int n = 0;
for(; A[n] != 0 ; ++n);
b[n] = 0;
c[n] = 0;
repm(i,n-1,-1){
b[i] = b[i+1] | (1<<(A[i]-'a'));
c[i] = c[i+1];
while(b[i] & (1<<c[i])) ++c[i];
if(c[i] == 26) b[i] = c[i] = 0;
}
for(int i = 0; i < n ; ++i){
char x = c[i] + 'a';
printf("%c" , x);
while(i < n && A[i] != x) ++i;
}
printf("\n");
return 0;
}解法まとめ
文字列$A$を後ろから見ていき、まだ現れていない英小文字のうち辞書順最小のもの$c_i$を求める。
但しすべての英小文字が現れたらリセットし、なかったものとして扱う。(12-17行)
文字列の先頭から最後にリセットされた位置の直前の区間での問題を解くとその答えは$c_0$である。
その後、文字列を先頭から$c_0$が初めに現れた直後までの文字を削除する。
文字列がなくなるまで繰り返すと解が得られる。(18-22行)