2017/10/12の精進

・ARC 081E Don't Be a Subsequence

文字列Aを末尾から見ていってa-zが全て現れるごとにくぎっていく

するとAは[a-zのすくなくとも1文字が無い区間][a-zがある区間][a-zがある区間]...[a-zがある区間]に分割される

ここで[a-zがある区間]がk個取れたとすると、Aの部分列でないような最小の列の長さはk+1である

[証明]

長さk以下の任意の列は明らかにAの部分列なのでAの部分列でないような列の長さはk+1以上であり、あとはAの部分列でないような長さk+1文字の列があることを示せばいい

ここで[1番目の区間に含まれないある1文字][2番目の区間の先頭の文字]...[k+1番目の区間の先頭の文字]を並べた列を考えると、これはそのような例になっている

(何故なら1文字目は2番目の区間から取り、2文字目は3番目の区間から取り...とやっていくとk+1文字目はどこからも取れないから)

よって示せた

あとは、Aの部分列でないような長さk+1の列のうち辞書順最小のものを求めることになる

細かい説明は省略するが、これは貪欲にとっていくことで出来る