ARC081E Don't Be a Subsequence
atcoder.jp
最近解いて面白かったので、考察の流れを書きます。
600埋め一覧
問題概要
（問題文は短いので、↑のリンクから見た方が良さそう）
文字列Aの部分列でない最短（複数ある場合は辞書順最小）な文字列を求めよ。
｜A｜ ≦2*10^5
文字は英小文字のみを考える．
考察
小さく考えてみる．
A="aba"かつ、文字は'a', 'b'のみの場合。
愚直に候補を並べていくと
"a", "b", "aa", "ab", "ba", "bb", "aaa", ...
Aの部分列でない最短は"bb"である。
ところで、ある文字列がA="aba"の部分列でないかを調べるオートマトンは次のようになる。
（最近オートマトンに触れてなかったので正しく書けてるか怪しい。）
1つのエッジは文字を意味している。
◎に到達した場合、それまでのパスを通ってできる文字列はAの部分列でない。
最短で◎に到達するパスは次の通り。
"bb"なら2ステップで◎に到達して最短。
文字が'a', 'b', 'c'の3種類だと、オートマトンは次のようになる。
この場合は"c"が最短な部分列でない文字列になる。
このことから、(1)オートマトンを作って、(2)◎までの最短経路を求めれば良さそうなことがわかる。
(1) オートマトンを作る
このオートマトンは「あるインデックスにおいて、次にくる文字種のインデックス」と同様。
文字列を後ろから見ていく感じのDPで作れる。
(2)◎までの最短経路を求める
これはBFS（をすると辞書順最小にもなります。）
計算量もO(文字種*文字列の長さ)くらいになりそうなので問題なさそう。
やったぜ。
おわりに
オートマトンやBFSみたいな、学校の講義で聞くようなテクが出てきて面白かったので考察の流れを書きました。
けど、ACしてるコードを調べたら色々な解き方があるっぽい。
もっと短く賢く書けるコードもあるので、そういうコードをササッと書けるようになりたいですね。
